백준 알고리즘 2750 (수 정렬하기) - C++, Python

[문제] 백준 알고리즘 2750 (수 정렬하기)

> https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

삽입 정렬이나 거품 정렬을 구현하는 문제이다. (시간 복잡도 O(N^2))

삽입 정렬(insert sort)은 작은 것을 최대한 앞쪽으로 삽입하는 방식이다.

 

[위키백과 - 삽입 정렬의 예]

(Bold는 값 비교 후 왼쪽>오른쪽 경우 교체)

idx = 0,   5 2 3 4 1 -> 2 5 3 4 1

idx = 1,   2 5 3 4 1 -> 2 3 5 4 1 -> 2 3 5 4 1

idx = 2,   2 3 5 4 1 -> 2 3 4 5 1 -> 2 3 4 5 1 -> 2 3 4 5 1

idx = 3,   2 3 4 5 1 -> 2 3 4 1 5 -> 2 3 1 4 5 -> 2 1 3 4 5 -> [1 2 3 4 5]  

 

거품 정렬(bubble sort)는 큰 것을 맨 뒤로 빼면서 제외하는 방식이다.

 

[위키백과 - 삽입 정렬의 예]

(Bold는 값 비교 후 왼쪽>오른쪽 경우 교체)

idx = 0,  5 2 3 4 1 -> 2 5 3 4 1 -> 2 3 5 4 1 -> 2 3 4 5 1 -> 2 3 4 1 [5] 5 fix

idx = 1,   2 3 4 1 -> 2 3 4 1 -> 2 3 4 1 -> 2 3 1 [4] 4 fix

idx = 2,   2 3 1 -> 2 3 1 -> 2 1 [3] 3 fix

idx = 3,   2 1 -> [1 2]      

 

코드로는 ins_sort()와 bub_sort()의 함수로 구분지어서 둘 다 구현했다.

 

 

[C++]

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 1000;
int arr[MAX],  n;

void bub_sort() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - i- 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
	return;
}

void ins_sort() {
	for (int i = 1; i < n; i++) {
		int j = i;
		while (j > 0) {
			if (arr[j - 1] > arr[j]) {
				int tmp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tmp;
			}
			j--;
		}
	}
	return;
}

int main() {
	memset(arr, 0, sizeof(arr));
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	//bub_sort();
	ins_sort();

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

 

[Python]

import sys
input = sys.stdin.readline
n = int(input())
arr = [int(input()) for _ in range(n)]
def ins_sort():
    for i in range(1, n):
        j = i
        while j > 0:
            if arr[j] < arr[j-1]:
                tmp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = tmp
            j -= 1
    return

def bub_sort():
    for i in range(n-1):
        for j in range(n - i - 1):
            if arr[j] > arr[j+1]:
                tmp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = tmp
    return

#bub_sort()
ins_sort()
for i in range(n):
    print(arr[i])