티스토리 뷰

selection sort와 bubble sort는 그 원리와 구현이 쉬워 학부 1학년 기초 컴퓨터 프로그래밍 수업)에서 배운다.

Selection Sort

주어진 배열에서 최솟값을 선택하고, 그 값을 맨 앞의 값과 비교해 교체하는 알고리즘이다.

example {23, 78, 45, 8, 32}

  1. min = 8 -> 23과 비교 -> {8, 78, 45, 23, 32}
  2. min = 23 -> 78과 비교 -> {8, 23, 45, 78, 32}
  3. min = 32 -> 45와 비교 -> {8, 23, 32, 78, 45}
  4. min = 45 -> 78과 비교 -> {8, 23, 32, 45, 78}
  5. min = 78 -> 78과 비교 -> {8, 23, 32, 45, 78}

이 과정을 시각화하면 아래 이미지처럼 보인다.

selection sort

C로 구현하면 이렇다:

int arr1[5] = {23, 78, 45, 8, 32};
int arr2[5] = {23, 78, 45, 8, 32};

int min = 0;
int temp = 0;

for(int i = 0; i < 5; i++) {
  min = i;
  for(int j = i; j < 5; j++) {
    if(arr1[min] > arr1[j]) {
      min = j;
    }
  }

  temp = arr1[i];
  arr1[i] = arr1[min];
  arr1[min] = temp;
}

O(n^2) 시간이 걸린다.

Bubble Sort

두 개의 인접한 요소를 비교해 교체하는 알고리즘이다.

example {23, 78, 45, 8, 32}

  1. 23과 78비교 -> {23, 78, 45, 8, 32}
  2. 78과 45비교 -> {23, 45, 78, 8, 32}
  3. 78과 8비교 -> {23, 45, 8, 78, 32}
  4. 78과 32비교 -> {23, 45, 8, 32, 78}
  5. 23과 45비교 -> {23, 45, 8, 32, 78}
  6. 45와 8비교 -> {23, 8, 45, 32, 78}
  7. 45와 32비교 -> {23, 8, 32, 45, 78}
  8. 23과 8비교 -> {8, 23, 32, 45, 78}
  9. 23과 32비교 -> {8, 23, 32, 45, 78}
  10. 8과 23비교 -> {8, 23, 32, 45, 78}
  11. 8과 8비교 -> {8, 23, 32, 45, 78}

코드로 구현하면 다음과 같다:

int arr1[5] = {23, 78, 45, 8, 32};
int arr2[5] = {23, 78, 45, 8, 32};

int min = 0;
int temp = 0;

for(int i = 0; i < 5; i++) {
  for(int j = 0; j < 4; j++) {
    if(arr2[j] > arr2[j + 1]) {
      temp = arr2[j];
      arr2[j] = arr2[j + 1];
      arr2[j + 1] = temp;
    }
  }
}

selection sort처럼 O(n^2) 시간이 걸린다.

댓글
댓글쓰기 폼