[자료구조와 함께 배우는 알고리즘 입문] 6. 정렬 알고리즘 (1)

1. 정렬 알고리즘이란?

 

1-1. 정렬이란?

정렬은 다들 알고 있는 것처럼 데이터를 순서에 따라 나열하는 것이다.

정렬 알고리즘을 이용해 데이터를 정렬하면 데이터 검색이 조금 더 쉬워지게 된다.

 

1-2. 정렬 알고리즘의 안정성

정렬 알고리즘은 안정된 알고리즘 / 안정되지 않은 알고리즘으로 나눌 수 있다.

안정된 정렬은 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것이다.

 

1-3. 내부 정렬과 외부 정렬

내부 정렬은 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때 사용하는 알고리즘이다.

외부 정렬은 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때 사용하는 알고리즘이다.

외부 정렬의 경우 알고리즘이 복잡해지고 별도의 팔일 등이 요구된다.

 

1-4. 정렬 알고리즘의 핵심요소 : 교환, 선택 삽입

 

 

2. 버블 정렬, 단순 교환 정렬

 

2-1. 버블정렬 알아보기

버블정렬은 이웃한 두 요소의 대소 관계를 비교하고 교환을 반복하는 알고리즘이다.

위와 같은 방식으로 정렬이 될 때 까지 데이터들 간의 교환을 해주는 것이다.

이런 과정들을 '패스' 라고 한다.

 

 

2-2. 버블 정렬 프로그램 만들기

    static void swap(int[] a, int idx1, int idx2){
        int temporay = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temporay;

        //idx1의 데이터 값을 임시 변수에 저장하고
        //idx1과 idx2데이터 교환
    }

    static void bubbleSort(int[] a, int n){
       int k=0;
       while (k<n-1){
           int last = n-1;
               for (int j = n-1; j >k ; j--) {
                   if(a[j-1]>a[j]){
                       swap(a,j-1,j);
                       last = j;
                   }
               }
               k=last;
       }

    }