얌생

배열 - 메모리상에 원소를 연속하게 배치한 자료구조다.

배열의 성질

• O(1)에 k번째 원소를 확인 및 변경이 가능
• 추가적으로 소모되는 메모리의양( =overhead )가 거의 없다.
• 메모리 상에 데이터들이 붙어있으므로 캐시 적중률이 높다
• 메모리 상에 연속한 구간을 잡아야 하므로 할당에 제약이 걸린다.

기능과 구현

• 임의의 위치에 있는 원소를 확인 하거나 변경할때 O(1)이 걸린다.
• 원소를 끝에 추가 = O(1)
• 마지막 원소를 제거 = O(1)
• 임의의 위치에 원소를 추가 / 임의 위치의 원소 제거 = O(N)

선택 정렬( Selection Sort )은 버블 정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 선택 정렬과 삽입 정렬를 헷갈릴 수 있는데, 선택 정렬은 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 된다.

선택 정렬은 3가지의 과정을 반복하며 정렬을 수행한다.

 1. 선택한 곳의 데이터보다 더 작은 데이터가 있는지 순환하며 찾는다.

 2. 구한 가장 작은 최솟값을 맨 앞에 위치한 값과 교체한다.

 3. 맨 앞의 위치를 하나씩 앞으로 옮겨가며 반복한다.

#include<iostream>
using namespace std;

int main()
{
	int Array[] = { 10,9,8,7,6,5,4,2,3,1 };
	int MinIndex;
	int Number;

	for (int i = 0; i < 9; i++)
	{
        // 맨 앞 위치 선택
		MinIndex = i;

		for (int j = i + 1; j < 10; j++)
		{
            // 선택한 위치 값과 다른 위치 값들비교
            // 더 작은 값이 있으면 위치값 갱신
			if (Array[MinIndex] > Array[j])
			{				
				MinIndex = j;
			}
		}
        
        // 한번 반복하고 나면 스왑
		swap(Array[i], Array[MinIndex]);
	}

	return 0;
}

시간복잡도

데이터의 개수가 n개라고 할 경우,

• 첫 번째 회전에서의 비교횟수 : 1 ~ ( n - 1 ) => n - 1
• 두 번째 회전에서의 비교횟수 : 2 ~ ( n - 1 ) => n - 2
• ...
• (n-1) + (n-2) + ... + 2 + 1 => n(n-1) / 2

비교하는 것이 상수 시간에 이루어진다는 가정 아래에서 n개의 주어진 배열을 정렬하는데

O( n^2 ) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 O( n^2 )로 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.

버블 정렬이란, 두 인접한 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 크면

자리를 바꾸는 정렬 알고리즘을 말한다.

이름의 유래는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

버블 정렬 알고리즘의 구체적인 방법

• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두번째 자료와 세 번째 자료를 .. 이런 식으로 ( 마지막 - 1 )번째 자료와 마지막 자료를 비교해 교환하면서 자료를 정렬한다.

void BubbleSort(int list[], int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			// 현재 위치와 앞 위치 데이터 비교
			// 현재 위치 데이터가 더 크면 스왑
			if (list[j] > list[j + 1])
			{
				swap(list[j], list[j + 1]);
			}
		}
	}
}

시간복잡도

시간복잡도를 계산하면, ( n - 1 ) + ( n - 2 ) + ( n -3 ) + .... + 2 + 1 => n(n-1)/2 이므로, O(n^2)다.

또한, Bubble Sort는 정렬이 되어있던 안되어있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두

시간 복잡도가 O(n^2)로 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.

장점

• 구현이 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. ( 제자리 정렬 )
• 안정 정렬(Stable Sort)이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
• 정렬 되어있지 않은 원소가 정렬 되었을때의 자리로 가기 위해, 교환 연산(swap)이 많이 일어나게 된다.