데이터를 특정한 기준에 따라서 순서대로 나열

1. 선택 정렬

매번 ‘가장 작은 것을 선택’

다른 정렬 알고리즘에 비해 비효율적

시간 복잡도 - O($N^2$)

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]

2. 삽입 정렬

특정한 데이터를 적절한 위치에 ‘삽입’

리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작

시간 복잡도 - O($N^2$)

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

3. 퀵 정렬

기준을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식

피벗Pivot(교환하기 위한 ‘기준’) 사용

호어 분할 방식 기준

• 리스트에서 첫 번째 데이터를 피벗으로
• 분할 or 파티션 : 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업

평균 시간 복잡도 - O($NlogN$)