[Algorithm] Bubble Sort 구현하기

Bubble Sort를 구현해보자


환경

  • Python
  • C++


Bubble Sort란?

원리

  • 인접한 2개의 값을 비교한후 값을 변경하는 과정을 통해서 정렬을 진행하는 알고리즘이다.
  • 오름차순의 경우라면 인접한 두 수를 비교했을 때 앞의 수가 더 크다면 그 둘의 값을 바꾸는 방식으로 아래의 사진을 보면 이해가 쉽다.

특징

  • 위에 사진처럼 왼쪽에서부터 오른쪽으로 진행하면서 정렬을 진행한다고 했을 때 1번 왼쪽에서 오른쪽까지 갈 때마다 가장 오른쪽에는 가장 큰 값이 위치하게 된다!
  • 코드의 구현은 쉬우나 복잡도가 O(n^2)의 성능을 나타낸다.


복잡도

  • 시간복잡도 : O(n^2)
  • 공간복잡도 : O(1)(swap을 위한 변수만 필요합니다.)


구현 코드(Python)


def merge_sort_better(A):

    for i in range(len(A) - 2, 0, -1):
        for j in range(0, i + 1):
            if A[j] > A[j + 1]:
                tmp = A[j]
                A[j] = A[j + 1]
                A[j + 1] = tmp

    return A


def merge_sort_normal(A):

    for i in range(0, len(A)):
        for j in range(0, len(A) - 1):
            if A[j] > A[j + 1]:
                tmp = A[j]
                A[j] = A[j + 1]
                A[j + 1] = tmp
    return A

import random
A = [random.randint(0, 100) for _ in range(0, 10)]
print(A)
merge_sort_better(A)
print(A)



구현 코드(C, C++)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

void bubble_sort_better(int a[], int len) {

	for (int i = len - 2; i >= 0; --i) {
		for (int j = 0; j <= i; ++j) {
			if (a[j] > a[j + 1]) {
				swap(&a[j], &a[j + 1]);
			}
		}
	}

}

void bubble_sort_normal(int a[], int len) {

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

}

int main() {

	int a[5];
	int len = sizeof(a) / sizeof(a[0]); // 배열길이

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 벡터 초기화
	for (int i = 0; i < len; i++) {
		// 1 ~ 50까지의 난수 생성
		a[i] = rand() % 50 + 1;
	}

	// 정렬 전 출력
	for (int i = 0; i < len; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");

	// 거품정렬
	bubble_sort_better(a, len);

	// 정렬 후 출력
	for (int i = 0; i < len; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}


참고자료

[Docker] 도커(Docker) 이미지 이름과 태그 목록 가져오기

> 도커(Docker) 이미지 이름과 태그 목록을 awk과 tail 명령어를 이용해 가져오는 방법을 알아보자## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Docker- awk, tail 명령어## 도커(Docker...… Continue reading