수 정렬하기(선택 정렬)

백준 2750

문제 링크

---

문제

---

문제 이해

1. 오름차순으로 정렬한다.
2. 수는 중복되지 않는다.

(1 ≤ N ≤ 1000)

---

💡문제 해결 과정

수를 정렬하는 알고리즘에는 여러 종류가 있다. 대표적인 것에는 다음과 같은 것들이 있다.

버블 정렬

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 크기가 순서대로 되어 있지 않으면 교환하면서 자료를 정렬한다.

출처 : Gyoogle

선택 정렬

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

출처 : Toptal

퀵 정렬

리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.(출처 : Wikipedia)

출처 : Gyoogle

오늘은 선택 정렬 알고리즘을 사용해 수를 정렬해보았다.

선택 정렬 알고리즘

1. arr배열 안에 n만큼 숫자를 담는다.

 int n, i, j, temp;
 int arr[1000];
 scanf("%d", &n);

 for (i = 0; i < n; i++) {
   scanf("%d", &arr[i]);
 }

2. 두 수를 바꾸는 swap 함수를 미리 만들어 준다.

void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

3. 가장 작은 값을 맨 처음에 놓는 작업을 반복한다.

for (int i = 0; i < n-1; i++) { //마지막 순서는 바꿀 필요 X
    for (int j = i + 1; j < n-1; j++) { //현재 순서 바로 다음 순서부터 비교 시작
      if (arr[i] > arr[j]) { //큰 값이 있으면       
        swap(&arr[i], &arr[j]); //swap
      }
    }
  }

4. 출력한다.

for (i = 0; i < n; i++) {
        printf("%d\n", arr[i]);
}

코드

#include <stdio.h>
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

int main(void) {
  int n, i, j, temp;
  int arr[1000];
  scanf("%d", &n);

  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
  //아래의 2중 for문이 선택 정렬 핵심.
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n - 1; j++) {
      if (arr[i] > arr[j]) {
        swap(&arr[i], &arr[j]);
      }
    }
  }

  for (i = 0; i < n; i++) {
    printf("%d\n", arr[i]);
  }
  return 0;
}

✅성능 및 결과

버블 정렬

선택 정렬