[DAY 09] Sort

1.1.1 정렬이란?

순서 없이 배열된 자료를 작은 것부터 큰 것 순서인 오름차순이나 큰 것부터 작은 것 순서인 내림차순으로 재배열하는 것

1.1.2 키(key)란?

자료를 정렬하는 데 사용하는 기준이 되는 특정값

1.2 정렬을 왜할까?

'검색' 때문!

검색을 얼마만큼 효율적으로 빨리 할 수 있느냐가 관건이다.

Bubble Sort(버블 정렬) : 

키를 비교하고 교환하여 정렬하는 방식(교환 방식)

버블 정렬(Bubble Sort)은 실무에서 많이 쓴다.

왜? 코드짜기 편하니까

But, 성능은 최악이다

 - "인접"한 원소를 두 개 비교하여 자리를 교환하는 방식을 반복하여 정렬한다.

 버블정렬을 수행하면 인접한 처음 두 개 원소부터 인접한 마지막 원소까지 비교하는 작업과 자리를 교환하는 작업을 반복하면서 가장 큰 원소가 마지막 자리에 정렬된다.

 첫째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 위로 뽀글뽀글 올라오는 물방울 모양과 같다고 해서 버블 정렬이라고 한다.

Program 09.01 Bubble Sort

---

#include <stdio.h>
 
void BubbleSort(int data[]);
void Printout(int data[]);
 
void main()
{
    int data[5] = { 90, 78, 100, 30, 55 };
    
    BubbleSort(data);
    Printout(data);
}
 
void BubbleSort(int data[])
{
    int i, j;
    int temp;
 
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4 - i; j++) {
            if (data[j] > data[j + 1]) {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
}
 
void Printout(int data[])
{
    int i;
 
    for (i = 0; i < 5; i++) {
        printf("%d \t", data[i]);
    }
    puts("");
}

.2 Selection Sort(선택 정렬) :

키를 비교하고 교환하여 정렬하는 방식(교환 방식)

 - 전체 원소 중에서 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식으로 정렬한다.

in Java... 선택정렬이란? 배열에서 아직 정렬되지 않은 부분의 원소들 중에서 최솟값을 '선택'하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 알고리즘이다.

 ★ 기준 위치가 1번째, 2번째, ... 순임

.3 Insertion Sort(삽입 정렬) :

키를 비교하고 삽입하여 정렬하는 방식(삽입 방식)

버블 정렬보다 살짝 빠르다.

삽입한 데이터는 정렬되어 있다고 간주한다

 - 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식으로 정렬을 수행한다.

in Java... 삽입정렬이란? 선택정렬과 유사하게 배열이 정렬된 부분과 정렬되지 않은 부분으로 나뉘며, 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분에 '삽입'하는 방식의 알고리즘이다.

Program 09.02 난수를 입력받아 오름차순으로 출력하는 Insertion Sort

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int RandNum(int flagChange);
void InsertionSort(int data[], int size);
void Printout(int data[]);
 
void main()
{
    int data[1000];
    int i;
 
    for (i = 0; i < 1000; i++) {
        data[i] = RandNum(1);
    }
 
    InsertionSort(data, 1000);
 
    for (i = 0; i <= 998; i++) {
        if (data[i] > data[i + 1]) puts("Error");
    }
 
    Printout(data, 1000);
}
 
int RandNum(int flagChange)
{
    if (flagChange == 1) {
        static int flag = 0;
        if (flag == 0) {
            flag = 1;
            srand((unsigned int)time(0));
        }
    }
 
    return rand();
}
 
void InsertionSort(int data[], int size)
{
    int i, j;
    int temp;
 
    for (i = 1; i < size; i++) {
        temp = data[i];
 
        for (j = i; j > 0; j--) {
            if (temp >= data[j - 1]) {
                data[j] = temp;
                break;
            } else {
                data[j] = data[j - 1];
                data[j - 1] = temp;
            }
        }
    }
}
 
void Printout(int data[], int size)
{
    int i;
 
    for (i = 0; i < size; i++) {
        printf("%d \t", data[i]);
    }
    puts("");
}

Binary Search

조건 : 무조건 정렬되어 있어야 한다!