개발 노트

정렬 알고리즘

 
  • Apr 17, 2020

Bubble Sort(거품 정렬)

버블 정렬 개요

거품 정렬은 배열의 모든 원소에 대해 첫 번째 원소부터 인접한 원소를 검사하여 정렬하는 방법입니다. 선택된 원소와 인접한 다음 원소를 비교하여 값이 크다면 위치를 교환합니다.

거품 정렬

모든 원소를 다음 원소들과 비교를 해가며 정렬을 하기 때문에 시간복잡도는 평균 O(n2) 입니다.

BubbleSort java 코드

import java.util.Arrays;

public class BubbleSort {
	public void sort(int[] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 1; j < array.length-i; j++) {
				if (array[j] < array[j - 1]) {
					int temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
				}
			}
		}
	}

	public static void main(String[] args) {
		int[] array = {9,8,7,6,5,4,3,2,1};

		BubbleSort sort = new BubbleSort();

		sort.sort(array);
		System.out.println(Arrays.toString(array));
	}
}

Insertion Sort(삽입 정렬)

삽입 정렬 개요

삽입 정렬은 배열의 모든 원소에 대해 앞에서부터 원소를 선택하여 자신보다 앞의 원소와 크기를 비교하여 위치를 찾아 삽입을 하는 정렬 방식입니다.

선택된 요소의 앞 요소부터 비교를 해야하므로 index 1에서 시작을 합니다.

삽입정렬

모든 원소를 선택하고 앞의 이미 정렬된 요소들과 비교를 해야하므로 시간복잡도는 평균 O(n2) 입니다.

InsersionSort java 코드

import java.util.Arrays;

public class InsertionSort {
	public void sort(int[] array) {
		for (int i = 1; i < array.length; i++) {
			for (int j = i; j > 0; j--) {
				if(array[j] < array[j-1]) {
					int temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		int[] array = {4,6,3,6,8,9,0,10,1,2};
		
		InsertionSort sort = new InsertionSort();
		
		sort.sort(array);
		System.out.println(Arrays.toString(array));
	}
}

Selection Sort(선택 정렬)

선택 정렬 개요

선택 정렬은 배열의 원소중에서 가장 작은 것을 선택하여 첫 번째 순서부터 넣는 방법입니다.

정렬 순서
  1. 첫 번째 위치에서 부터 가장 작은 원소를 찾는다.
  2. 첫 번째 위치에 넣는다.
  3. 두번째 자리에서 부터 가장 작은 원소를 찾는다.
  4. 두 번째 위치에 넣는다.
  5. 과정을 반복한다.

선택 정렬

선택 정렬도 최소 값을 찾는 위치를 결정하는 루프와 최소 값을 찾는 루프를 사용해서 시간복잡도는 평균 O(n2) 입니다.

Selection Sort java 코드

import java.util.Arrays;

public class SelectionSort {
	public void sort(int[] array) {
		for (int i = 0; i < array.length; i++) {
			int index = i;
			for (int j = i; j < array.length; j++) {
				if(array[index] > array[j]) {
					index = j;
				}
			}
			int temp = array[index];
			array[index] = array[i];
			array[i] = temp;
		}
	}
	
	public static void main(String[] args) {
		int[] array = {4,6,3,6,8,9,0,10,1,2};
		
		SelectionSort sort = new SelectionSort();
		sort.sort(array);
		System.out.println(Arrays.toString(array));
	}
}

Quick Sort(빠른 정렬)

빠른 정렬 개요

퀵 정렬은 분할 정복 알고리즘입니다. 피봇(pivot)을 선정하고 기준으로 하여 왼쪽에는 피봇 값 보다 작은 원소를 두고 오른쪽에는 큰 값을 두도록하여 정렬하는 방식입니다. 피봇으로 나누어진 왼쪽, 오른쪽을 재귀 함수를 이용해 다시 정렬합니다. 반복이 끝나면 작은 값은 왼쪽, 큰 값은 오른쪽에 모이게 되어 정렬이 완료됩니다.

정렬 과정

  1. 적당한 피봇을 선택합니다.
  2. 배열의 왼쪽부터 피봇보다 큰 원소가 있는 위치(i)를 찾는다. 오른쪽부터 피봇보다 작은 원소가 있는 위치(j)를 찾는다.
  3. 양쪽의 위치를 찾았으면 서로 원소의 위치( i <-> j )를 바꾸어준다.
  4. i가 j 보다 커질때 까지 반복한다.
  5. 피봇을 기준으로 나누어진 배열을 기준으로 재귀 함수로 과정을 반복한다.

퀵 정렬은 피봇 선택에 따라 성능이 좌우됩니다. 최악의 경우 O(n2)의 시간복잡도이며 최선의 경우 균등하게 분포되어 O(nlogn)의 시간복잡도입니다.

Quick Sort java 소스코드

import java.util.Arrays;

public class QuickSort {
	public void quickSort(int[] data, int start, int end){
        int left = start;
        int right = end;
        int pivot = data[(start + end)/2];
        
        while (left <= right) {
            while(data[left] < pivot) 
              left++;
            while(data[right] > pivot) 
              right--;
            if(left <= right){    
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        } 
        
        if(start < right) 
          quickSort(data, start, right); 
      
        if(end > left) 
          quickSort(data, left, end); 
    }

	public static void main(String[] args) {
		QuickSort quick = new QuickSort();
		int[] array = {5,4,3,2,4,5,7,8};
		quick.quickSort(array, 0, array.length-1);
		
		System.out.println(Arrays.toString(array));
	}
}
Search