[자료구조] 정렬

Yeooooooni·2021년 8월 23일

자료구조

목록 보기

1/1

정렬의 분류

안정성에 따른 분류
1) Stable sort
-정렬 순서가 동일한 원소에 대해 초기 순서를 유지하는 정렬
- bubble
- insertion
- merge
- radix
- counting
  2) Unstable sort
- selection
- quick
- heap
- shell
비교 여부에 따른 분류
1) 비교 정렬
2) 비비교 정렬
-ex) counting, radix sort

정렬의 종류

1. bubble

: 이웃한 두 원소 중 큰 것을 뒤로 보내 정렬하는 방법

void bubbleSort(int [] arr){
	for (int i = 1 ; i < arr.length ; i++){
    		for (int j = 0 ; j < arr.length - i ; j++){
        		if(arr[j]>arr[j+1])
            			swap(arr, j, j+1);
        	}		
    	}
}

O(n^2)

2. selection

: 정렬되지 않은 원소 중 최솟값을 찾아 정렬된 부분 뒤에 위치시켜 정렬하는 방법

void selectionSort(int [] arr) {
	for ( int i=0 ; i < arr.length ; i++){
    		int min = arr[i];
        	int minIdx;
    		for ( int j = i+1 ; j < arr.length ; j++){
        		if(arr[j] < min){
            			min = arr[j];
                		minIdx = j;
            		}
        	}
        swap( arr, i, minIdx);
    }
}

O(n^2)

3. insertion

: 정렬된 부분에서 정렬되지 않은 첫 번째 원소가 들어갈 위치를 찾아 삽입하는 정렬 방법

void insertionSort(int [] arr){
	for( int i = 1 ; i < arr.length ; i ++){
    		int insertedData = arr[i];
    		for(int j = i-1 ; j >= 0 ; j--){
        		if(arr[j] > insertedData){
                		arr[j+1] = arr[j];
                	} else {
                    		break;
                    	}
        	}
            	arr[i] = insertedData;
        }
}

O(n^2)

4. quick

: 피벗을 중심으로 좌측은 피벗보다 작은 원소, 우측은 피벗보다 큰 원소로 분류함으로써 정렬하는 방법

void quickSort(int [] arr, int left, int right){
	if(left >= right ) return;
    int pivot = left;
    int i = left + 1 ;
    int j = right ;
    do { 
    	while(i < right && arr[i] < arr[pivot]) i++;
        while(j > left && arr[j] > arr[pivot]) j--;
        if(i < j)
        	swap(arr, i, j);
    }while(i<j);
    swap(arr, j, pivot);
    quickSort(arr, left, j-1);
    quickSort(arr, j+1, right);
}