정렬 알고리즘①(버블,선택,삽입,퀵)

정렬 (Sorting)은 데이터를 일정한 기준(오름차순, 내림차순 등)에 따라 정렬하는 과정을 의미합니다.
빠르고 효율적인 정렬 알고리즘을 선택하는 것이 중요하며, 
정렬 방식에 따라 시간 복잡도와 공간 복잡도가 달라집니다.

 

1. 버블 정렬 (Bubble Sort)

○ 옆에 있는 값과 비교하여 교환하는 방식

○ 큰 값이 계속 오른쪽으로 이동합니다. (마치 거품처럼 떠오르는 느낌)

void BubbleSort(int[] arr)
{
	int n = arr.Length;
    for(int i=0; i<n-1; i++)
    {
    	for(int j=0; j<n-i-1; j++)
        {
        	if(arr[j] > arr[j+1])
            {
            	//Swap
                (arr[j], arr[j+1]) = (arr[j+1], arr[j]);
            }
        }
    }
}

✅ 단순하지만 매우 비효율적 입니다.

✅ 거의 정렬된 경우 최적화가 가능합니다.

 

 

2. 선택 정렬 (Selection Sort)

○ 가장 작은 값을 선택하여 정렬

○ 첫 번째 요소부터 시작하여 가장 작은 값을 찾아서 앞으로 이동합니다.

void SelectionSort(int[] arr)
{
	int n = arr.Length;
    for(int i=0; i<n-1; i++)
    {
    	int minIndex = i;
        for(int j=i+1; j<n; j++)
        {
        	if(arr[j] < arr[minIndex])
            	minIndex = j;
        }
        // Swap
        (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
    }
}

✅ 제자리 정렬 (in-place sorting)

✅ 시간 복잡도 O(n²)로 비효율적입니다.

 

3. 삽입 정렬 (Insertion Sort)

○ 현재 요소를 올바른 위치에 삽입합니다

○ 왼쪽은 이미 정렬된 상태 입니다.

void InsertionSort(int[] arr)
{
	int n = arr.Length;
    for(int i=1; i<n; i++)
    {
    	int key = arr[i];
        int j = i-1;
        while(j>=0 && arr[j] > key)
        {
        	arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

✅ 거의 정렬된 데이터에 대해는 빠릅니다 (O(n))

✅ 삽입과 이동 연산이 많아 큰 데이터에서는 비효율적입니다(O(n²))

 

4. 퀵 정렬 (Quick Sort)

○ 피벗(Pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다.

○ 분할 정복 (Dovode & Conquer) 기법을 사용합니다.

void QuickSort(int[] arr, int left, int right)
{
	if(left < right)
    {
    	int pivotIndex = Partition(arr. left, right);
        QuickSort(arr, left, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, right);
    }
}

int Partition(int[] arr, int left, int right)
{
	int pivot = arr[right];
    int i = left - 1;
    
    for(int j=left; j<right; j++)
    {
    	if(arr[j] < pivot)
        {
        	i++;
            (arr[i], arr[j]) = (arr[j], arr[i]);
        }
    }
    (arr[i+1], arr[right]) = (arr[right], arr[i+1]);
    return i+1;
}

✅ 평균 O(n log n)으로 매우 빠름

✅ 최악의 경우 O(n²) 발생 가능합니다.

 

 

2편으로...

 

 

긴 글 읽어주셔서 감사합니다
도움이 되셨다면 공감 & 댓글 응원 부탁드립니다