python 선택정렬, 삽입정렬, 퀵정렬

 

이것이 코딩테스트다 with 파이썬 참고자료

선택정렬
데이터가 무작위로 여러개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.

array = [7,5,9,0,3,1,6,2,4,8]

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]
print(array)

---

삽입정렬
특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입된다는 점이 특징이다.

array = [7,5,9,0,3,1,6,2,4,8]

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
print(break)

---

퀵 정렬
기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

array = [5,7,9,0,3,1,6,2,4,8]

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 = [x for x in tail if x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))