정렬 알고리즘 - 선택 정렬, 삽입 정렬

정렬 알고리즘

데이터 요소들을 특정한 순서대로 재배치 하는 방법을 다루는 중요한 주제이다.

• 정렬(Sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말합니다.
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

---

선택 정렬(Selection Sort)

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선책해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
• 선택 정렬은 N번만큼 반복해야 한다.
• 평균 및 최악의 시간 복잡도는 O(n^2)이다. 선택 정렬은 단순하게 이해할 수 있으나 대규모 데이터에는 비효율적일 수 있다.

array = [7,4,5,9,1,2,3]
​
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)

 

출력 결과 : [1, 2, 3, 4, 5, 7, 9]

 

< python 코드 상세 설명 >

array 리스트를 정의한다. 첫 번째 for 루프: 리스트의 길이만큼 반복한다. i는 현재 정렬된 부분의 마지막 원소의 인덱스이다. min_index 변수는 가장 작은 원소의 인덱스를 나타낸다. 두 번째 for 루프: 현재 i 다음 원소부터 리스트의 끝까지 반복합니다. 현재까지의 가장 작은 원소의 인덱스 min_index와 비교하여, 더 작은 원소를 찾으면 min_index를 업데이트한다. 내부 루프가 종료되면, 현재의 최솟값을 찾는다. 현재 정렬된 부분의 마지막 원소인 array[i]와 최솟값인 array[min_index]를 교환(swap)한다. 현재 정렬된 부분에 가장 작은 원소가 추가되게 된다. 첫 번째 for 루프의 다음 반복으로 넘어간다. 모든 반복이 완료된 후, 리스트가 정렬된 상태로 출력된다.

---

삽입 정렬(Insertion Sort)

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
• 선택 정렬에 비해 더 빠르게 정렬, 현재 리스트의 데이터가 거의 정렬되어 잇는 상태라면 매우 빠르게 동작한다.
• 첫번째 데이터는 그 자체로 정렬 되어 있다고 판단하고 두번째 데이터가 첫번째 데이터의 왼쪽으로 들어갈지 오른쪽으로 들어갈지 판단한다. (매번 위치를 바꿔가면서 정렬)

array = [7,4,5,9,1,2,3]
​
for i in range(1, len(array)):
 	for j in range(i, 0, -1): # 인덱스 i 부터 1까지 1씩 감소하며 반복하는 문법
 	if array[j] < array[j - 1] # 한칸씩 왼쪽으로 이동
		 array[j], array[j -1] = array[j - 1],array[j]
	 else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
 		break
​
print(array)

출력 결과 : [1, 2, 3, 4, 5, 7, 9]

 

<python 코드 상세 설명 >

array 리스트를 정의한다. 두 번째 for 루프: 정렬되지 않은 부분의 첫 번째 요소부터 시작하여, 정렬된 부분으로 적절한 위치에 삽입할 때까지 역순으로 반복한다. 현재 요소 array[j]가 이전 요소 array[j - 1]보다 작다면, 두 요소를 스와핑하여 한 칸씩 왼쪽으로 이동한다. 만약 자신보다 작은 데이터를 만나면 스와핑을 멈추고, 삽입할 위치를 찾아 정렬된 부분에 삽입한다. 첫 번째 for 루프의 다음 반복으로 넘어간다. 모든 반복이 완료된 후, 리스트가 정렬된 상태로 출력된다.