정렬 알고리즘(08.9.17 ~ 10.2)

1. 개요

    정렬 알고리즘들을 통해서 효율적인 알고리즘을 분석한다.

    (버블, 머지, 퀵)

 

2. 개발환경

    - 이클립스 JAVA

    - GUI : Jigloo

 

3. 소스

   가. 버블 정렬 알고리즘

펼쳐두기..

public class BubbleSort {
    void bubble(int arr[], int n){
        boolean flag = false;
        for (int i=1; (i<n) && (!flag); ++i){ - - - - - - - - - 1
            flag=true;
            for(int k=0; k<n-i; ++k){- - - - - - - - - - - - - - 2
                if (arr[k]>arr[k+1]){
                    int temp = arr[k];
                    arr[k] = arr[k+1];     - - - - - - - - - - - -  3
                    arr[k+1]=temp;
                    flag = false; - - - -- - - - - - - - - - - - - - 4
                }
            }
        }
    }
}

   나. 머지 정렬 알고리즘

펼쳐두기..

void mergeSort(int[] arr, int l, int r) {
        if (r<=l) return;
        int m = (r+l) / 2; - - - - 1 : r, l의 중간 지점 계산
        mergeSort(arr, l, m); - - 2 : 전반부 정렬
        mergeSort(arr, m+1, r);-3 : 후반부 정렬
        merge(arr, l, m, r);- - - -4 : 병합
}
 void merge(int[] arr, int l, int m, int r) {
        int i, j;
        for (i=m+1; i>l; i--) temp[i-1]=arr[i-1]; - - 5
        for (j=m; j<r; j++) temp[r+m-j]=arr[j+1];- 6
        for (int k=l; k<=r; k++)
            if (temp[j]<temp[i])
                arr[k]=temp[j--];        - - - - - - - - - 7
            else
                arr[k]=temp[i++];
}

 

   다. 퀵 정렬 알고리즘

펼쳐두기..

void Quick(int arr[], int first, int last){
        if(first<last){
            int Pivot = Partition(arr, first, last);- 분할
            Quick(arr, first, Pivot-1);- - - - - - - - 왼쪽 정렬
            Quick(arr, Pivot+1, last);- - - - - - - - 오른쪽 정렬
        }
}
int Partition(int arr[], int first, int last){
        int low, high, p, temp;
        p = arr[last]; - - - - - - - - - - - - - - 기준 원소
        low = first-1; - - - - - - - - - - - - - - 1구역 끝지점     
        for(high=first; high<=last-1; high++){
            if(arr[high]<=p){             high는 3구역 시작지점
                temp=arr[++low];
                arr[low]=arr[high];   - -기준보다 작으면 교환
                arr[high]=temp;
            }
        }
        temp=arr[low+1];
        arr[low+1]=arr[last];  - 기준과 2구역 첫 숫자와 교환
        arr[last]=temp;              
        return low+1;
}

 

4. 실행화면

처음에 이 프로젝트 과제가 나왔을때 인터페이스를 어떻게 할지 고민이 많았다.

그래서 생각한것이 그래프도 넣고 n값이 커질경우 시간이 오래걸릴수있으니 그것을 나타내어주는

프로그래스바도 만들었다. 프로그램내에 각각의 알고리즘 소스를 프로그램 실행화면에서도

보여주게하고 결과창을 만들어서 각각 정렬알고리즘을 비교하여보았다.

 

N값을 넣고 실행하엿을때 값이 나타나는것이 프로그램이 멈추었다가 한번에 나타나는 현상이 있어서

스레드를 이용하여 해결했던 기억이 있다.