[Algorithm]기본적인 정렬 알고리즘

선택정렬

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

시간 복잡도

Best : O(n^2)

Avg : O(n^2)

Worst : O(n^2)

소스 코드

int[] a = new int[]{2,4,1,3,6,7,5,8,10,9};
for(int i=0;i<a.length-1;i++){
            int min = i;
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[min]){
                    min=j;
                }
            }
            swap(a,min,i);
        }
 System.out.println(Arrays.toString(a));

버블정렬

버블 정렬(Bubble Sort)은 인접한 두개의 원소를 비교하여 자리를 교환하는 방식으로 정렬

첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막자리로 이동하는 모습이

물속에서 물 위로 올라오는 물방울 모양과 같다고 해서 버블 정렬이라고 한다

시간 복잡도

Best : O(n^2)

Avg : O(n^2)

Worst : O(n^2)

소스 코드

int[] b = new int[]{2,4,1,3,6,7,5,8,10,9};
ffor(int i=0; i<b.length-1;i++){
             for(int j=0;j<b.length-1;j++){
                 if(b[j]>b[j+1]){
                     swap(b,j,j+1);
                 }
             }
         }
 System.out.println(Arrays.toString(b));

삽입정렬

삽입 정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

시간 복잡도

Best : O(n)

Avg : O(n^2)

Worst : O(n^2)

소스 코드

int[] c = new int[]{2,4,1,3,6,7,5,8,10,9};
for(int i=1; i<c.length;i++){
             int j=i;
             int temp=c[i];
             while(j>0&&c[j-1]>temp){
                 c[j]=c[j-1];
                 j--;
             }
             c[j]=temp;
         }
System.out.println(Arrays.toString(c));

퀵정렬

분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 왼쪽 부분 집합과 오른쪽 부분집합을 정렬 하는 방법

1. 전체원소 가운데 하나의 원소를 중심(Pivot)으로 2개의 부분 집합으로 분할 한다.

2. 기준값(Pivot) 보다 작은 원소는 왼쪽 부분집합으로, 기준값(Pivot) 보다 큰 원소들은 오른쪽 부분 집합으로 정렬한다.

3. 분할된 부분집합의 크기가 0이나 1이 될 때 까지 순환 호출을 이용하여 다시 분할 한다.

시간 복잡도

Best : O(nlogn)

Avg : O(nlogn)

Worst : O(n^2)

소스 코드

public int pivot(int[] array, int start, int end){
        int middle = array[(start+end)/2];
    while(start<end) {
        while (array[start] < middle && start < end) start++;
        while (array[end] > middle && start < end) end--;
        if (start < end) {
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
        }
    }
        return start;
}

 public void quicksort(int[] array,int start,int end ){
        if(start<end){
            int middle = pivot(array,start,end);

            quicksort(array, start,middle-1);
            quicksort(array,middle+1,end);
        }

}
int[] d = new int[]{2,4,1,3,6,7,5,8,10,9};
@Test
public void sort(){
    quicksort(d,0,d.length-1);
    System.out.println(Arrays.toString(d));
}