'Algorithm&DataStructures/Sorting'에 해당되는 글 4건

퀵 정렬  - Quick Sorting

- 다른 정렬 알고리즘에 비해 빠르다

- 분할, 정렬 알고리즘 사용(divide and conquer)

- pivot 이라는 요소를 지정하고 나누어 각각 리스트를 비교한 후 합친다

- 재귀함수 호출 사용

- 다른 알고리즘에 비해 복잡하게 느껴진다(me too...)

1. QuickSorting.class

1) 초기화

private int[] arry; private int length;

- 배열, 배열 크기를 정의

2) sort()

public void sort(int[] arry){ this.arry = arry; this.length = arry.length; quickSort(0, length-1); }  

- 생성자 함수와 같이 값을 초기화 한다

- 퀵 정렬 호출

3) quickSort()

private void quickSort(int lowIndex, int highIndex){ int pivot = arry[(lowIndex+(highIndex - lowIndex)/2)]; int low = lowIndex; int high = highIndex; //pivot을 기준으로 리스트를 분할 한다 while(low <= high){ //pivot 보다 작은 값이라면 계속진행, 크다면 멈추고 low에 값이 저장된다 while(pivot > arry[low]){ low++; } //pivot 보다 큰 값 while(pivot < arry[high]){ high--; } //만약 low가 high 보다 크다면, 그것은 pivot을 기준으로 양쪽 값이 잘 정렬됬다는 것을 뜻 한다, 위치 바꿀 필요없음 if(low <= high){ //위에서 멈춘 위치의 값들을 서로 교환한다 exchange(low,high); //교환했다면 다시 진행을 위해 증가/감소 한다 low++; high--; } } print(); if(lowIndex < high){ quickSort(lowIndex, high); } if(low < highIndex){ quickSort(low, highIndex); } }  

4) exchange(), print()

public void exchange(int low, int high){ int temp = arry[low]; arry[low] = arry[high]; arry[high] = temp; } public void print(){ for(int i = 0; i< length; i++){ System.out.print(arry[i]+" "); } System.out.println(); }  

- 값 교환하는 부분과 상태를 표시

5) main()

public static void main(String[]args){ QuickSorting aa = new QuickSorting(); int bb[] = {10,2,3,99,1,7,-1,100}; for(int a: bb){ System.out.print(a+" "); } System.out.println(); aa.sort(bb); }  

인서트정렬 - Insertion sorting

- 작은 양에 데이터를 비교할 때 적합하다

- 간결하고 효율적이다

1. InsertionSorting.class

1) insert(int[] arry)

public void insert(int[] arry){ print(arry); //배열의 크기의 -1 만큼 회전 for(int i = 1; i<arry.length; i++){ //i의 값에 따라 값 비교를 시작 하기 때문에 --로 진행 for(int j = i; j>0; j--){ if(arry[j] < arry[j-1]){ swap(arry,j); } } System.out.print("-"+i+" "); print(arry); } }

- 배열의 크기 -1만큼 회전한다

- 한번 회전 할때 마다 처음 회전 횟수를 기준으로 비교

(i = 1 이면 한번 비교, i = 2 요소 값 3개 두번 비교 i =3 이면 요소값 네개 세번 비교....)

- 버블 정렬과 비슷해보이지만 버블 정렬은 1회전에 모든 값을 돌면서 비교 하지만 인서트는 회전 할 때마다 비교값이 제한 되어있다

2) swap(int[] arry,  int j), print(int[] arry)

public void swap(int[] arry, int j){ int temp = 0; temp = arry[j]; arry[j] = arry[j-1]; arry[j-1] = temp; } public void print(int[] arry){ for(int b : arry){ System.out.print(b+" "); } System.out.println(); }  

- 값의 위치를 변경 해주는 함수와 상태 값 출력

3) main()    

public static void main(String[] args){ InsertionSorting aa = new InsertionSorting(); int[] bb= {1,10,5,2,30,0,-5}; aa.insert(bb); }  

선택 정렬(Selection sorting) - Selection sorting

- 검색(searching) + 정렬(sorting) 이 함께 있는 구조이다

1. SelectionSorting.class

1) selection(int[] arry)

public static void selection(int[]arry){ //배열 크기만큼 회전 for(int i = 0;i<arry.length; i++){ int index = i; //첫 번째 다음 요소 부터 검색을 시작한다 for(int k = i+1; k<arry.length; k++){ //검색을 해서 가장작은 값을 찾으면 인덱스를 저장 if(arry[index] > arry[k]){ index = k; } } //가장 작은 값과 맨 앞의 값을 교환 swap(i,index,arry); print(arry); } }

- 정렬을 시작한다

- 버블 정렬과는 다르게 마지막 for을 다 마친 후에 저장된 인덱스 번호로 swap을 한다

2) swap(int i, int k, int[]arry), print(int[] arry)

public static void swap(int i, int k, int[]arry){ int temp; temp = arry[k]; arry[k] = arry[i]; arry[i] = temp; } public static void print(int[]arry){ for(int i = 0; i<arry.length; i++){ System.out.print(arry[i]+","); } System.out.println(); }  

3) main()

public static void main(String[]args){ int[] input = {2,3,10,1,-5}; selection(input); }  

버블정렬 - bubble sorting

- 회전을 하면서 앞뒤의 요소들을 비교한다

- 앞의 요소가 크다면 바로 뒤의 요소와 위치를 변경한다

1. BubbleSorting.class

1) bubble_sort()

public static void bubble_sort(int arry[]){ int n = arry.length; int k; //배열 크기만큼 회전을 한다 for(int i = 0; i<n; i++){ //배열보다 하나 작은 크기로 버블 정렬이 시작된다 for(int l = 0; l< n-1; l++){ k = l + 1; //앞뒤 요소를 비교, 앞이 크면 위치를 변경한다 if(arry[l] > arry[k]){ swap(l,k,arry); } } print(arry); } }

- 정렬하는 함수

2) swap()

public static void swap(int i, int k, int[]arry){ int temp; temp = arry[i]; arry[i] = arry[k]; arry[k] = temp; }  

- 앞의 요소가 더 크다면 위치를 뒤에 요소와 변경한다

3) print()

public static void print(int[]arry){ for(int i = 0; i<arry.length; i++){ System.out.print(arry[i]+","); } System.out.println(); }  

- 정렬 상태를 반영한다

4) main()

public static void main(String[]args){ int[] input = {4,5,1,2,7}; bubble_sort(input); }