정렬알고리즘[선택,삽입,퀵,합병,셀_..힙,기수]

package sortExample;

public class Sort {

private int[] sortedArray;

public Sort(int[] data) {

this.sortedArray = data;

}

private void printArray(){

for(int k=0; k<sortedArray.length; k++){

            System.out.print(sortedArray[k]+" ");

        }

System.out.print("\n");

}

public void selectionSort(int[] array){

int min; //인덱스를 가리킬 녀석

int temp; //임시 저장 변수

for(int i = 0; i < array.length-1; i++){

min = i;

for(int j = i+1; j < array.length; j++){

if(array[min] > array[j]){

min = j ;

}

}//안에 있는 for문

//안에 있는 for문이 모든 루틴을 돌고난 후 교환

temp = array[i];//현재 정렬하려고 했던 인덱스에 있는 값을 임시로 temp변수에 저장

array[i] = array[min];//정렬되지 않는 범위에서 제일 작은 값을 정렬하고자 했던 위치에 대입

array[min] = temp;

printArray();

}//밖에 있는 for문

} 

public void bubbleSort(int[] array){

int temp;

for(int i = array.length-1; i >=0 ; i--){//i가 한개씩 감소해서 비교하는 이유 끝에서부터 하나씩 정렬되기 때문에

for(int j = 0; j < i; j++){

if(array[j] > array[j+1]){

temp = array[j];

array[j] = array[j+1];

array[j+1] = temp;

}

printArray();

}//안에 있는 for문

}//밖에 있는 for문

}

//for문 방법

public void insertSort1(int[] array){

int temp;

int j;//for문 지역변수가 아닌 for문 밖 지역으로 빼야함.

for(int i = 1; i < array.length; i++){

temp = array[i];

for(j = i-1; j >= 0 && temp < array[j]; j--){

array[j+1] = array[j];

}

array[j+1] = temp;

printArray();

}//밖에 있는 for문

}

//while문 방법

public void insertSort2(int[] array){

int temp;

int j;

for(int i = 1; i < array.length; i++){

temp = array[i];

j = i;

while(j > 0 && array[j-1] > temp ){

array[j] = array[j-1];

j = j-1;

}

array[j] = temp;

printArray();

}//밖에 있는 for문

}

}

package sortExample;

public class SortTest {

public static void main(String[] args) {

// TODO Auto-generated method stub

int data[] = {66, 10, 1, 99, 5};

Sort sort = new Sort(data);

printArray(data);

//sort.selectionSort(data);

//sort.bubbleSort(data);

//sort.insertSort1(data);

sort.insertSort2(data);

printArray(data);

}

public static void printArray(int[] data){

System.out.print("\n");

       for(int i=0; i<data.length; i++){

           System.out.print("data["+i+"] : " + data[i]+"  ");

       }

       System.out.print("\n");

}

}

선택정렬

현재 정렬되지 않는 부분에서 제일 작은 값을 찾아 첫번째 위치에 교환하고

또 그다음으로 작은 값을 정렬되지 않은 부분에서 찾아 두번째 위치에 교환하는 방식으로

작은값들을 찾아 선택해 0번인덱스부터 채워나가는 방식입니다.

시간의 복잡도는 배열이 사전에 어떻게 있는지 상관없이 n^2이고 

공간복잡도는 n입니다.

삽입정렬

삽입정렬은 말그대로 자신의 위치를 찾아서 삽입되는 방식입니다.

우선 삽입될 대상의 값을 임시 temp에 저장해놓고 temp에 저장되어있는 값과 자신의 인덱스 앞쪽에 있는 값들과 비교를 하여 자신의 위치를 찾아 들어갑니다. 

시간의 복잡도는 최악의 경우 즉 역으로 정렬될 경우로 n^2이고 이미 정렬되어있는 경우 n입니다.

공간복잡도는 n입니다. 

합병정렬

분할정복방식으로 정렬을 하는 방식입니다. 우선 4개의 배열이 있다고 하면, 4개조각으로 쪼개고 1번째와 2번째를 머지하면서 정렬을 합니다. 또 3번째4번재를 머지하여 정렬을 하고 이제 2개의 머지된 정렬을 또다시 머지하면서 정렬을 합니다. 

이러한 방식으로 분할정복 정렬을 해나갑니다.

시간의 복잡도는 nlogn이고 

공간복잡도는 2n입니다.

버블정렬

매번 인접한 두개의 값을 비교하여 큰값이 맨마지막으로 위치하는 방식으로 끝에서부터 정렬되는 방식을 취합니다.

시간의 복잡도는 n^2이고

공간복잡도는 n입니다.

퀵 정렬

퀵정렬을 일반적으로 가장 빠르다고 알려져 있는 정렬이고,  피봇 즉 기준을 잡아 그 기준보다 작으면 왼쪽 크면 오른쪽으로 모는 방식을 통해 분할된 배열의 크기가 1이되면, 완료되는 분할정복방식을 취합니다.

시간의 복잡도는 nlogn이고, 최악의 경우 이미정렬되어있는 경우 n^2이다.

셀정렬

삽입정렬의 비효율적인 부분을 보완하기 위해 탄생했습니다.

배열의 크기에서 /2를 나눈 값으로 인터벌을 정하고, 인터벌 간격만큼 비교를 하여 사전에 

배열을 정렬합니다. 이런식으로 인터벌이 1이 될때까지 사전에 미리 정렬시키고난 다음

마지막으로 삽입정렬을 수행하게 합니다.

시간의 복잡도는 최악의 경우 n^2이고 최선의 경우 n^1.5입니다.

히프정렬