[Algorithm] 버블 정렬 vs 선택 정렬 vs 삽입 정렬의 동작 방식과 시간 복잡도!

반응형

 

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 

💋 버블 정렬(Bubble Sort)

✔️ 개념

가장 간단한 정렬 알고리즘 중 하나로, 반복적으로 인접한 두 원소를 비교해서 정렬 순서에 따라 교환하는 과정을 반복한다.

 

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

 

✔️ 동작 방식

왼쪽부터 순차적으로 이웃한 원소를 비교하고, 더 큰 값을 오른쪽으로 이동시킨다.

이렇게 하면 처음에는 가장 큰 원소인 6이 가장 오른쪽 끝으로 이동하게 된다.

 

 

그 다음에는, 두 번째로 큰 원소인 5를 찾아 그것을 오른쪽에서 두 번째에 배치하게 된다.

 

 

위 과정을 데이터가 정렬될 때까지 반복된다.

 

 

✔️ 구현

 

간단하게 아래와 같이 구현할 수 있다.

 

// Optimized java implementation of Bubble sort

import java.io.*;

class GFG {
	
	// An optimized version of Bubble Sort
	static void bubbleSort(int arr[], int n)
	{
		int i, j, temp;
		boolean swapped;
		for (i = 0; i < n - 1; i++) {
			swapped = false;
			for (j = 0; j < n - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					
					// Swap arr[j] and arr[j+1]
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					swapped = true;
				}
			}

			// If no two elements were
			// swapped by inner loop, then break
			if (swapped == false)
				break;
		}
	}

// This code is contributed
// by Nikita Tiwari.

 

✔️ 시간 복잡도

배열의 원소들을 각 pass마다 N-1, N-2, N-3, …번 비교해야 한다.

최악의 경우(오름차순으로 정렬해야 하는데 현재 내림차순으로 정렬되어 있는 경우) 모든 원소들을 서로 교환해야 한다.

 

• Total no. of passes: n-1
• Total no. of comparisons: n*(n-1)/2

 

따라서, 시간복잡도는 O(N^2) 이다. ⇒ 거의 구석기시대 정렬방식

 

 

✔️ 공간 복잡도

정렬을 위해서 별도의 메모리 공간이 필요하지는 않다. ⇒ O(1)

 

💋 선택 정렬(Selection Sort)

✔️ 개념

 

 

리스트에서 가장 작은 값을 선택하여 맨 앞에 이동시키는 방식으로 동작하는 정렬 방식이다.

 

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.

 

✔️ 동작 방식

리스트를 돌아다니면서 가장 작은 값인 11을 찾고, 11을 리스트의 맨 앞으로 옮긴다.

 

 

이제 11은 정렬된 부분이므로 다음 pass 때는 제외된다.

다음 정렬되지 않은 부분을 돌아다니면서 가장 작은 값인 12를 찾고, 12를 정렬되지 않은 부분의맨 앞으로 옮긴다.

 

 

 

이제 11, 12는 정렬된 부분이므로 다음 pass 때는 제외된다.

 

이렇게 과정을 반복하다보면, 모든 영역이 정렬된 부분이 되면서 정렬이 완료된다.

 

 

✔️ 구현

 

// Java program for implementation of Selection Sort

import java.io.*;

public class SelectionSort
{
	void sort(int arr[])
	{
		int n = arr.length;

		// One by one move boundary of unsorted subarray
		for (int i = 0; i < n-1; i++)
		{
			// Find the minimum element in unsorted array
			int min_idx = i;
			for (int j = i+1; j < n; j++)
				if (arr[j] < arr[min_idx])
					min_idx = j;

			// Swap the found minimum element with the first
			// element
			int temp = arr[min_idx];
			arr[min_idx] = arr[i];
			arr[i] = temp;
		}
	}
}
/* This code is contributed by Rajat Mishra*/

 

✔️ 시간 복잡도

N-1번의 사이클을 반복하고, 각 사이클 내에서 다른 원소들과 N-1, N-2, N-3, … 번의 비교를 하게 된다.

 

• Total no. of passes: n-1
• Total no. of comparisons: n*(n-1)/2

 

따라서, 시간복잡도는 O(N^2) 이다. ⇒ 역시나 구석기 시대 정렬 방식

 

 

그래도, 원소를 교환(swap)하는 관점에서는, 한 번의 사이클마다 딱 1번의 swap만 하면 된다. 이 점에서 selection sort가 bubble sort보다 최대 2배 빠를 수 있다. (그래도 시간 복잡도는 같음.)

 

✔️ 공간 복잡도

bubble sort와 마찬가지로, 정렬을 위해서 별도의 메모리 공간이 필요하지는 않다. ⇒ O(1)

 

 

 

💋 삽입 정렬(Insertion Sort)

✔️ 개념

원소의 숫자보다 큰 숫자가 원소보다 왼쪽에 있으면 자리를 바꾸는 방식의 정렬 방식이다.

 

 

 

✔️ 구현

 

// Java program for implementation of Insertion Sort
public class InsertionSort {
	/*Function to sort array using insertion sort*/
	void sort(int arr[])
	{
		int n = arr.length;
		for (int i = 1; i < n; ++i) {
			int key = arr[i];
			int j = i - 1;

			/* Move elements of arr[0..i-1], that are
			greater than key, to one position ahead
			of their current position */
			while (j >= 0 && arr[j] > key) {
				arr[j + 1] = arr[j];
				j = j - 1;
			}
			arr[j + 1] = key;
		}
	}
};


/* This code is contributed by Rajat Mishra. */

 

✔️ 시간 복잡도

마찬가지로 N-1개의 원소들에 대해서 각각 N-1, N-2, N-3, … 번의 비교를 반복한다. ⇒ O(N^2)

 

 

하지만, 삽입 정렬은 이미 정렬된 부분과 비교를 하기 때문에, 필요한 아이템만 스캔하고 선택 정렬은 정렬되지 않은 부분에서 최소값을 찾기 위해 전체 모든 아이템을 스캔한다. ⇒ 삽입 정렬은 선택 정렬보다 빠르다.

그래도 둘의 시간 복잡도는 같다….

 

✔️ 공간 복잡도

정렬을 위해 별도의 메모리 공간은 필요하지 않다. ⇒ O(1)

 

💋 버블 정렬, 선택 정렬, 삽입 정렬은 모두 O(N^2)의 시간 복잡도면 같은 성능인가?!!

3가지 경우 모두 결과적으로 같은 시간 복잡도를 가지지만, 디테일하게 살펴보면 모두 속도가 다르다.

best, worst case보다는 average case에 대해서 자세히 알아봐야 한다.

 

이미지 출처: https://velog.io/@minji0801/%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%AC-vs-%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%AC-vs-%EC%82%BD%EC%9E%85%EC%A0%95%EB%A0%AC-%EC%B0%A8%EC%9D%B4-%EC%A0%9C%EB%8C%80%EB%A1%9C-%EC%95%8C%EA%B3%A0%EA%B0%80%EC%9E%90

 

대부분의 경우 두 가지 모두 O(n^2)의 시간 복잡도를 가지지만, 삽입 정렬의 경우에는 best case에서 O(n)의 시간 복잡도를 가진다.

 

이런 경우는, 이미 정렬된 배열이거나 거의 정렬된 배열인 경우이다.

삽입 정렬은 정렬된 부분 배열에서 새로운 원소를 삽입하는 방식으로 동작하는데, 이미 정렬된 배열에서는 새로운 원소를 비교해야 할 때, 비교를 중단하고 바로 다음 위치로 이동할 수 있기 때문에 비교 횟수가 많이 줄어들게 된다. 따라서 이미 정렬된 배열에서는 비교 횟수가 최소화되고 시간 복잡도가 O(n)이 될 수 있다.

 

 

 

💋 참고자료

• https://www.geeksforgeeks.org/bubble-sort/
• https://www.geeksforgeeks.org/selection-sort/
• https://www.geeksforgeeks.org/selection-sort-vs-bubble-sort/
• https://www.geeksforgeeks.org/insertion-sort/
• https://www.youtube.com/watch?v=Bor_CRWEIXo

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!