정렬 - 예제

버블 정렬

def bubble_sort(arr):
	for i in range(len(arr)-1, 0, -1):	# 마지막 index 에서부터 정렬
    	swapped = False
        
        for j in range(i):				# 첫번째 index 부터 정렬되지 않은 마지막 index 까지
        	if arr[j] > arr [j + 1]:	# 짝을 지어 값을 비교 후, 큰 값이 뒤에 위치하도록 swap
        		arr[j], arr[j + 1] = arr[j + 1 ], arr[j]
        		swapped = True
    	if not swapped:
    		break

#####  최적화  #####        
def bubble_sort(arr):
	end = len(arr) -1
    
    while end > 0:
    	last_swap = 0			# 마지막으로 swap 이 일어난 index 저장
    	for i in range(end):
    		if arr[i] > arr[i + 1]:
        		arr[i], arr[i + 1] = arr[i +1], arr[i]
            	last_swap = i
    	end = last_swap			# 중간을 건너뛰고 가장 마지막에 swap 이 일어난 index 부터 정렬 시작

선택 정렬

def selection_sort(arr):				# arr [ 6, 4, 1, 9, 3 ]
	for i in range(len(arr) -1): 		# 최소값의 index(= min_idx) 와 현재 index(= i) 의 값을 swap
    min_idx = i	
    for j in range(i + 1, len(arr)): 	# 현재 index 부터 마지막 index 중에 최소값의 index 를 검색
    	if arr[j] < arr[min_idx]:	
        min_idx = j
    arr[i], arr[min_idx} = arr[min_idx], arr[i]

삽입 정렬

def insertion_sort(arr):
	for end in range(1, len(arr)):			# 정렬 범위를 2 에서 n 으로 확대
    	for i in range(end, 0, -1):			# 정렬 범위에 새롭게 추가된 값과 기존 값들을 비교
        	if arr[i - 1] > arr[i]:			# 앞의 값과 뒤의 값을 비교, 앞의 값이 큰 경우 swap
            	arr[i - 1], arr[i] = arr[i], arr[i - 1]

#####  최적화  #####
# 새롭게 추가된 값보다 작은 값들은 이미 이전 패스에서 정렬이 완료되었으므로 while문 탈출
def insertion_sort(arr):
	for end on range(1, len(arr)):
    	i = end
        while i > 0 and arr [i - 1] > arr[i]:
        	arr[i - 1], arr[i] = arr[i], arr[i - 1]
            i -= 1

병합 정렬

# 배열을 복제하는 방식 ( 메모리 사용량 많음 )
def merge_sort(arr):
    if len(arr) < 2:						# 배열의 길이가 2보다 작아질 때까지 재귀적으로 호출
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])			# 왼쪽 배열
    high_arr = merge_sort(arr[mid:])		# 오른쪽 배열

    merged_arr = []							# conquer한 배열을 combine시킬 새로운 배열
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])	# 왼쪽 배열 값을 새로운 배열에 저장하고 한 칸 이동
            l += 1
        else:
            merged_arr.append(high_arr[h])	# 오른쪽 배열 값을 새로운 배열에 저장하고 한 칸 이동
            h += 1
    merged_arr += low_arr[l:]				# 왼쪽 배열에 남아있는 값을 먼저 combine
    merged_arr += high_arr[h:]				# 오른쪽 배열에 남아있는 값을 다음에 combine
    return merged_arr						# 정렬 완료	
    
#####  최적화  #####
# 인덱스 접근을 통해 배열을 업데이트 하는 방식 ( 제자리 정렬 )    
def merge_sort(arr):
    def sorter(low, high):
        if high - low < 2:
            return
            
        mid = (low + high) // 2
        sorter(low, mid)
        sorter(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):			# temp에 저장된 순서로 원본 배열을 수정
            arr[i] = temp[i - low]

    return sorter(0, len(arr))

퀵 정렬

대부분의 프로그래밍 언어에 내장된 sort 함수는 퀵 정렬이 default

def quick_sort(arr):
	if len(arr) <= 1:
    	return arr
        
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    
    for num in arr:
    	if num < pivot:
        	lesser_arr.append(num)
        elif num > pivot:
        	greater_arr.append(num)
        else:
        	equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
    
#####  최적화  #####
def quick_sort(arr):
    def sorter(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sorter(low, mid - 1)
        sorter(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]		# 리스트 정가운데의 pivot 선택
        while low <= high:					# if 문에서 상호 교대가 이루어지면 탈출
            while arr[low] < pivot:
                low += 1					# 시작 index 에서 1씩 증가하며, pivot 보다 큰 값 검색
            while arr[high] > pivot:		
                high -= 1					# 끝 index 에서 1씩 감소하며, pivot 보다 작은 값 검색
            if low <= high:
            # 두 index 가 교차하지 않았으면 low index의 값과 high index 값을 swap 후, 각자 진행 방향으로 한 칸씩 이동
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high - 1
        return low							# while 문을 탈출한 뒤 재귀 호출의 기준점이 될 시작 index 리턴

    return sorter(0, len(arr) - 1)

출처