- 삽입 정렬은 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입 하는 방법입니다.
- 선택정렬처럼 동작을 직관적으로 이해하기 쉽지만, 선택정렬보다는 구현 난이도가 높고 실행시간 면에서 더 효율적입니다.
i) 삽입 정렬 과정
삽입 정렬 과정
1) 삽입정렬은 이미 정렬된 영역( 검은색 박스 부분) 과 아직 정렬되지 않은 영역 ( 그 오른쪽 숫자들)로 나뉩니다.
2) 정렬은 두 번째 요소부터 자신의 왼쪽과 비교해 나가면서 한칸 씩 왼쪽으로 이동합니다.
3) 자신보다 작은 숫자를 찾는 순간 그 뒤에 자신을 삽입합니다.
ii) 삽입 정렬 특징
구현이 간단하고 이해하기 쉬운 알고리즘입니다.
배열의 크기가 작은 경우 효율적인 알고리즘이 됩니다.
이미 정렬된 배열에 요소를 추가하는 경우 효율적인 알고리즘이 됩니다.
최악의 경우 시간 복잡도가 O(n²)이므로 배열의 크기가 커질수록 비효율적인 알고리즘이 됩니다.
stable한 정렬입니다. 즉, 정렬된 결과에서 동일한 값의 순서가 변하지 않습니다.
iii) 삽입 정렬 파이썬 코드
- 위의 코드에서 range(1, len(arr))의 의미는 두 번째 요소부터 마지막 요소까지 확인하는 의미입니다.
- key 값에 해당하는 요소의 값을 저장한 후 밑의 while 문에서 arr[j+1] = arr[j]로 값을 넣어주고 while문이 나올 때 arr[j+1] = key 를
통해서 값의 위치를 바꿔줄 수 있습니다.
- for 문이 다 돌아가면 오름차순 정렬된 값을 확인해 볼 수 있습니다.
💡선택 정렬
- 선택 정렬은 배열을 정렬하는 알고리즘 중 하나로, 배열에서 가장 작은 값을 찾아 첫 번째 위치와 교환하고, 그 다음으로 작은 값을 찾아 두 번째 위치와 교환하는 과정을 반복하여 전체 배열이 정렬될 때까지 반복하는 알고리즘입니다.
i) 선택 정렬 과정
선택 정렬 과정
ii) 선택 정렬 특징
구현이 간단하고 이해하기 쉬운 알고리즘입니다.
정렬이 필요한 배열의 크기가 작을 경우 효율적인 알고리즘이 됩니다.
최악의 경우 시간 복잡도가 O(n²)이므로 배열의 크기가 커질수록 비효율적인 알고리즘이 됩니다.
iii) 선택 정렬 파이썬 코드
- 위의 코드는 선택 정렬을 구현한 것으로, 입력받은 배열을 정렬한 후 정렬된 배열을 반환합니다. 코드에서 n은 배열의 길이를 나타내고,
min_idx는 현재까지 탐색한 부분 배열에서 가장 작은 값의 인덱스를 저장합니다.
- for문을 반복하면서 가장 작은 min_idx를 찾아 맨 앞과 위치를 바꿔가면서 정렬합니다.
- 최종적으로 선택정렬로 정렬된 배열의 값은 arr = [11, 12, 22, 25 ,64]가 나온다.
💡버블 정렬
-버블 정렬이란 인접한 두 원소를 비교하면서 정렬을 수행하는 방식으로 동작하는 것을 말합니다.
i) 버블 정렬 과정
버블 정렬 과정
- 리스트의 첫 번째 원소부터 인접한 두 원소를 비교합니다.
- 두 원소의 순서가 잘못되어 있으면 위치를 교환합니다.
- 리스트의 끝까지 위의 단계를 반복합니다.
- 리스트의 끝까지 반복하면 가장 큰 원소가 리스트의 마지막 위치에 위치하게 됩니다.
- 마지막 위치에 있는 원소를 제외하고 위의 과정을 반복합니다.
- 리스트의 크기가 1이 될 때까지 위의 과정을 반복합니다.
ii) 버블 정렬 특징
버블 정렬은 구현이 간단하고 이해하기 쉽습니다. 인접한 두 원소를 비교하여 위치를 교환하는 단순한 방식으로 정렬을 수행하기 때문입니다.
버블 정렬은 안정 정렬입니다. 안정 정렬이란, 정렬 이후에 같은 값을 가진 원소들이 정렬 전의 순서와 동일하게 유지되는 것을 의미합니다. 따라서, 버블 정렬은 원소의 상대적인 순서가 중요한 경우에 사용할 수 있습니다.
버블 정렬은 최악의 경우 시간 복잡도가 O(n^2)입니다. 따라서, 정렬할 데이터의 크기가 커질수록 성능이 저하되며 대용량 데이터에 대한 정렬에는 적합하지 않습니다.
버블 정렬은 제자리 정렬(in-place sort)입니다. 즉, 정렬할 배열 외에는 추가적인 메모리를 사용하지 않습니다. 이는 메모리 사용량이 적은 장비에서 사용할 수 있게 만듭니다.
만약 정렬할 데이터가 이미 정렬되어 있는 경우, 버블 정렬은 더 이상 교환을 하지 않고 정렬이 끝나게 됩니다. 이 경우 시간 복잡도는 O(n)이 됩니다. 하지만, 이 경우에도 데이터의 크기가 크면 성능이 좋지 않을 수 있습니다.
iii) 버블 정렬 파이썬 코드
위의 코드에서의 핵심은 두 개의 반복문입니다. 바깥쪽 반복문은 배열의 길이만큼 반복하면서, 배열에서 아직 정렬되지 않은 부분 중 가장 큰 원소를 배열 끝으로 이동시킵니다. 안쪽 반복문은 배열의 길이에서 바깥쪽 반복문의 인덱스를 뺀 것 만큼 반복하며, 인접한 두 원소를 비교하여 위치를 교환합니다.