• 목차

Description

• 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘을 공식처럼 사용

1️⃣ 선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

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

for i in range(len(array)) : 
	# 1. 가장 작은 원소의 인덱스
	min_index = i

	# 2. 처리되지 않은 데이터 중
	for j in range(i+1, len(array)) :

		# 3. 가장 작은 데이터를 선택
		if array[j] < array[min_index] :
				min_index = j
	
	# 4. 선택된 가장 작은 데이터와 맨 앞에 있는 데이터와 교환
	array[i], array[min_index] = array[min_index], array[i]

2️⃣ 삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작

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

for i in range(1, len(array)) :
	# 1. 인덱스 i부터 1까지 1씩 감소하며 반복
	for j in range(i, 0, -1) :

		# 2. 왼쪽 인덱스가 자신보다 크다면, 스와프
		if array[j] < array[i] :
				array[j], array[i] = array[i], array[j]

		# 3. 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
		else :
				break

3️⃣ 퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 피벗 설정, 스왑, 분할과정을 재귀적으로 수행