[Python] 정렬 - 선택, 삽입, 퀵

오름차순 기준으로 정렬

내림차순: 오름차순을 뒤집기 with 시간복잡도 O(N)

 

선택정렬

• 가장 작은 것을 선택해서 맨 앞 원소와 swap하는 과정을 N-1번 반복
• 매번 가장 작은 원소를 찾기 위해 비교 연산 해야함 - 시간복잡도 O(N^2)

  for i in range(len(array)):
  	min_index = i
      for j in range(i+1, len(array)):
      	if array[min_index] > array[j]:
          	min_index = j
      array[i], array[min_index] = array[min_index], array[i]​

삽입정렬

• 선택정렬처럼 직관적으로 이해하기 쉬운 알고리즘, 실행 시간 측면에서 더 효율적
• O(N^2) - 현재 리스트의 데이터가 거의 정렬되어 있는상태라면 매우 빠르게 동작
• 정렬되어 있는 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입됨
• 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요없이 그 자리에 삽입됨

  for i in range(1, len(array)):
  	for j in range(i, 0, -1):
      	if array[j] < array[j-1]:
          	array[j], array[j-1] = array[j-1], array[j]
          else:
          	break​

   

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 (왼쪽에서)큰 데이터와 (오른쪽에서)작은 데이터의 위치를 바꿈
• 왼쪽에서부터 찾은 값과 오른쪽에서 찾는 값의 위치가 서로 엇갈린 경우 - 작은 데이터와 피벗의 위치를 서로 변경
• 파티션으로 분할되고 각 파티션을 위의 과정처럼 정렬
• 정렬 라이브러리의 근간 - 시간복잡도 O(NlogN)

  def quick_sort(array):
  	if len(array) <= 1:
      	return array
      pivot = array[0]
      tail = array[1:]
      
      left_side = [x for x in tail if x<=pivot]
      right_side = [xfor x in tail if x>pivot]
      
      return quick_sort(left_side) + [pivot] + quick_sort(right_side)​

   

계수정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
  • 데이트가 정수 형태로 표현할 수 있을 때
  • 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000넘지 않을 때
• 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있는 리스트 생성 후, 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가

[python] sorted()함수

• 퀵 정렬과 동작 방식이 비슷한 병합 정렬 기반으로 만들어짐
• 최악의 경우 시간 복잡도 O(NlogN)

참고

[책] 이것이 취업을 위한 코딩 테스트이다