Sort

📗 Sort

• O(n²)의 시간 복잡도
  - 버블 정렬(Bubble Sort)
  - 선택 정렬(Selection Sort)
  - 삽입 정렬(Insertion Sort)
• O(n log n)의 시간 복잡도
  - 병합 정렬(Merge Sort)
  - 퀵 정렬(Quick Sort)

🔔 버블 정렬(Bubble Sort)

• 인접한 두 수를 비교하며 정렬하는 방법
• 앞 또는 뒤에서부터 반복하여 작은 수부터 큰 수로 정렬 가능

arr = [9,8,7,6,5,4,3,2,1]
def bubble_sort(arr):
	n = len(arr)
    for i in range(n-1):
    	for j in range(n-i-1):
        	if arr[j] > arr[j+1]:
            	arr[j], arr[j+1] = arr[j+1], arr[j]

🔔 선택 정렬(Selection Sort)

• 한 바퀴 돌때마다 가장 작은 값을 찾아 맨 앞과 교환하며 정렬하는 방법
• 앞에서부터 정렬한다는 특성이 있음

arr = [8,4,6,2,9,1,3,7,5]
def selection_sort(arr):
	n = len(arr)
    for i in range(n):
    	min_index = i
        for j in range(i+1, n):
        	if arr[j] < arr[min_index]:
            	min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

🔔 삽입 정렬(Insertion Sort)

• 정렬된 데이터 그룹을 늘리며 추가되는 데이터를 알맞은 자리에 삽입하며 정렬하는 방식

arr = [8,4,6,2,9,1,3,7,5]
def insertions_sort(arr):
	n = len(arr)
    for i in range(1, n):
    	for j in range(i, 0, -1):
        	if arr[j-1] > arr[j]:
            	arr[j-1], arr[j] = arr[j], arr[j-1]

🔔 병합 정렬(Merge Sort)

• 분할 정복과 재귀를 이용하여 비교적 낮은 시간 복잡도를 가져 앞의 방식들보다 성능이 좋음
• 반으로 나누고 다시 합치는 과정에서 그룹으로 정렬하게 되며 2n개의 공간이 필요함

arr = [8,4,6,2,9,1,3,7,5]
def merge_sort(arr):
	if len(arr) < 2:
    	return arr
    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])
    merge_arr = []
    l, h = 0, 0
    while l < len(low_arr) and h < len(high_arr):
    	if low_arr[l] < high_arr[h]:
        	merge_arr.append(low_arr[l])
            l += 1
        else:
        	merge_arr.append(high_arr[h])
            h += 1
    merge_arr += low_arr[l:]
    merge_arr += high_arr[h:]
    return merge_arr

🔔 퀵 정렬(Quick Sort)

• 병합 정렬과 동일하게 분할 정복 알고리즘으로 비교적 빠른 속도로 수행함
• 추가적인 메모리 공간이 필요없음
• pivot을 설정하고 그 기준에 따라 분할함, 병합 정렬은 균등하게 분할한다는 차이가 있음

arr = [8,4,6,2,9,1,3,7,5]
def quick_sort(arr):
	if len(arr) < 1:
    	return arr
    pivot = len(arr) // 2
    f_arr, p_arr, b_arr = [], [], []
    for value in arr:
    	if value < arr[pivot]:
        	f_arr.append(value)
        elif value > arr[pivot]:
        	b_arr.append(value)
        else:
        	p_arr.append(value)
    return quick_sort(f_arr) + quick_sort(p_arr) + quick_sort(b_arr)

🔔 sort() VS sorted()

• sort() : list.sort()
  • 입력값으로 리스트만 받을 수 있음
  • 리스트의 원본값을 직접 수정함
  • 정렬을 수행한 리스트를 따로 반환하지 않음
• sorted() : sorted(list, key)
  • 리스트 원본 값은 유지함
  • 어떤 입력값이든 받을 수 있음
  • 정렬 작업을 수행한 후의 값을 반환함
• sorted() 함수는 Timsort 알고리즘을 이용함

📘 관련 문제

⭐ K번째수
⭐ 가장 큰 수
⭐ H-Index