수 정렬하기(버블 정렬)

백준 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 (i = n - 1; i >= 0; i--) {
        for (j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j],&arr[j+1]);
            }
        }
    }

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() {
    int n, i, j, temp;
    int arr[1000];

    scanf("%d", &n);

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

    for (i = n - 1; i >= 0; i--) {
        for (j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j],&arr[j+1]);
            }
        }
    }

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

    return 0;
}

✅성능 및 결과