[알고리즘] 기본 정렬 알고리즘(삽입 정렬, 선택 정렬, 버블 정렬)

정렬 알고리즘 이란

- 원소들을 일정한 순서대로 열거하는 알고리즘입니다.

 

- 대표적인 알고리즘에는 아래와 같이 존재합니다. 

- 병합 정렬, 힙 정렬, 퀵 정렬의 경우 다음 포스팅에서 확인하시면 될 것 같습니다.

• 삽입 정렬 (Insertion sort)
• 선택 정렬 (Selection sort)
• 버블 정렬 (Bubble sort)
• 병합 정렬 (Merge sort)
• 힙 정렬 (Heap sort)
• 퀵 정렬 (Quick sort)

 

 

 

💡삽입 정렬

 

- 삽입 정렬은 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입 하는 방법입니다.

- 선택정렬처럼 동작을 직관적으로 이해하기 쉽지만, 선택정렬보다는 구현 난이도가 높고 실행시간 면에서 더 효율적입니다.

 

 

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) 버블 정렬 파이썬 코드

 

 

위의 코드에서의 핵심은 두 개의 반복문입니다. 바깥쪽 반복문은 배열의 길이만큼 반복하면서, 배열에서 아직 정렬되지 않은 부분 중 가장 큰 원소를 배열 끝으로 이동시킵니다. 안쪽 반복문은 배열의 길이에서 바깥쪽 반복문의 인덱스를 뺀 것 만큼 반복하며, 인접한 두 원소를 비교하여 위치를 교환합니다.

 

 

 

 

Reference

- 삽입 정렬 : https://hyen4110.tistory.com/54

- 선택 정렬 : https://hyen4110.tistory.com/53

- 버블 정렬 : https://data-marketing-bk.tistory.com/m/entry/Python%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%93%9C-%EB%B0%8F-%EC%98%88%EC%8B%9C%EB%A1%9C-%EB%A7%88%EC%8A%A4%ED%84%B0-%ED%95%98%EA%B8%B0