[이코테] 정렬 알고리즘

정렬 알고리즘의 종류

1. 선택 정렬 - 기본 but 시간 복잡도 높다
2. 삽입 정렬 - 선택 정렬보다는 시간 복잡도가 낮다. 정렬이 어느정도 되어있는 data 에 대해 특히 빠른 편이다.
3. 퀵 정렬 - 시간 복잡도가 낮다. 하지만 이미 정렬된 data에 대해서는 느리다.
4. 계수 정렬 - 범위가 한정적인 data에 대해 적용가능하며 시간 복잡도 매우 낮다.
   
   
   
   

접근 방식

• sorted(array)나 array.sort()라이브러리를 사용하자
• BUT IF 데이터의 범위가 한정적(ex. 성적)이라면 계수 정렬이 더 빠르다
• • 정렬 알고리즘을 직접 묻는 문제의 경우 당연히 선택, 삽입, 퀵 중에서 어떤 정렬 알고리즘을 사용해야하는지 적절히 골라 사용할 수 있어야 한다.
• 그러니까 소스 코드를 어느정도 암기해두자. 특히 계수정렬!
  
  
  
  

계수정렬 소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1) 
for i in range(len(array)):
	count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가 
    
for i in range(len(count)):
	for j in range(count[i]):
    	print(i, end = ' ')

기타

• lambda 함수를 sorted()의 key 인자에 잘 활용하자

  • 기본 문법: lambda 매개변수: 결과
  • 예시
    • add = lambda x, y : x+y
      result = add(3,5)
    • array = sorted(array, key = lambda student : student[i])

• input_data = input().split()의 결과 : 문자열을 원소로 하는 1차원 리스트

• for문 밖으로 뺄 수 있는 건 최대한 빼자

• sort와 sorted함수의 reverse 인자 활용하자