[정렬] 버블 정렬 | 삽입 정렬 | 선택 정렬

목차

1. 정렬

2. 버블 정렬

3. 삽입 정렬

4. 선택 정렬

 

---

 

1. 정렬

  - 특정 값을 기준으로 데이터를 순서대로 배치하는 방법

  - 구현 난이도는 쉽지만, 속도는 느린 알고리즘

      - 버블 정렬, 삽입 정렬, 선택 정렬

  -  구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘

      - 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬

  - 하이브리드 정렬

      - 팀 정렬, 블록 병합 정렬, 인트로 정렬

  - 기타 정렬 알고리즘

      - 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬

 

 * 인플레이스 정렬 : 제자리 정렬, 추가적인 메모리 필요 없이 메모리 공간 내에서 해결 (버블, 삽입, 선택)

 

2. 버블 정렬 (Bubble Sort)

  - 인접한 데이터를 비교하며 자리 바꾸는 방식

  - 한번 정렬 할 때 결국 가장 큰 수가 가장 마지막으로 가게 되기 때문에 그 다음 정렬 때는 마지막 - 1로 진행

  - 알고리즘 복잡도 : O(n^2)

 

2-1. 버블 정렬 구현

  - 의사 코드 (Pseudocode) : 알고리즘 flow 파악 용 (실제 돌아가는 코드 X)

bubbleSort(arr[]) {     arr[SIZE]      for i = 1 to SIZE - 1 {           for j = 0 to SIZE - i {                if (arr[j] > arr[j + 1])                     swap (arr[j], arr[j + 1])           }      } }

 

 

 

3. 삽입 정렬 (Insertion Sort)

  - 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식

  - 한번 정렬 할 때 결국 제일 작은 수가 맨 앞으로 오기 때문에 그 다음 정렬때는 맨 앞 + 1부터 시작

  - 알고리즘 복잡도 : O(n^2)

 

3-1. 삽입 정렬 구현

  - 의사 코드 (Pseudocode)

 

insertionSort(arr[]) {      arr[SIZE]      for i = 1 to SIZE {           for j = i to 0 (j--) {                if (arr[j] < arr[j - 1])                     swap (arr[j], arr[j - 1])             }       } }

 

 

 

4. 선택 정렬 (Selection Sort)

  - 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식

  - 한번 정렬할 때 최소값이 제일 앞으로 오기 때문에 다음 정렬할 때 최소값을 찾아 맨 앞 + 1 까지 비교

  - 알고리즘 복잡도 : O(n^2)

 

4-1. 선택 정렬 구현

  - 의사 코드 (Pseudocode)

selectionSort(arr[]) {      arr[SIZE]      for i = 0 to SIZE - 1 {           min = i           for j = i + 1 to SIZE {                if (arr[j] < arr[min])                     min = j            }           swap (arr[i], arr[min])      } }