Study Room

순차 검색은 일렬로 되어 있는 자료를 처음부터 마지막까지 순서대로 검색하는 방법으로 선혈 검색(Linear Search)이라고도 한다. 순차 검색은 가장 간단하고 직접적인 방법으로 배열이나 연결 리스트로 구현된 선형 자료 구조에서 원하는 항목을 찾는 방법이다. 순차 검색은 검색해야 하는 자료의 양에 따라 효율이 달라지기 때문에 자료가 아주 많은 경우에는 비효율적이지만, 알고리즘이 단순하여 구현이 쉬운 장점이 있다.

- 정렬되지 않은 순차 자료 구조에서의 순차 검색

첫 번쨰 원소부터 시작하여 마지막 원소까지 순서대로 키값이 일치하는 원소가 있는지를 비교하여 찾는다. 키값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환한다. 마지막 원소까지 비교하여 키값이 일치하는 워소가 없으면 검색실패

시간복잡도 : O(n)

public class sequentialSearch1 {

public static void main(String[] args) {

int a[]={8,30,1,9,11,19,2};

int size=a.length;

sequentialSearch(a,size,9);

sequentialSearch(a,size,10);

}

static void sequentialSearch(int a[], int n, int key)

{

int i;

for(i=0 ; i<n ;i++){

if(a[i]==key) {

break;

}

}

if(i<n){

System.out.println(i+1+"번째에서 검색 성공");

}

else System.out.println("검색 실패");

}

}

- 정렬되어 있는 순차 자료 구조에서의 순차 검색

정렬되어 있지 않은 자료에서 순차 검색을 하는 경우에 검색 실패는 마지막 원소까지 모두 비교한 후에야 알 수 있다. 하지만 정렬되어 있는 자료에 대해 순차 검색을 할 경우에는 원소의 키값이 찾는 키값보다 크면 찾는 원소가 없는 것이므로 더 이상 검색을 수행하지 않고 끝낼 수 있다.

시간복잡도 : O(n)

public class sequentialSearch2 {

public static void main(String[] args) {

int a[]={1,2,8,9,11,19,29};

int size=a.length;

sequentialSearch(a,size,8);

sequentialSearch(a,size,6);

}

static void sequentialSearch(int a[], int n, int key) {

int i=0;

if(i<n){

while( a[i]<key) i++;

}

if( a[i]==key){

System.out.println(i+1+"번째에서 검색 성공");

}

else System.out.println(i+1+"번째에서 검색 실패");

}

}

병합 정렬은 여러 개의 정렬된 자료의 집합을 겹합하여 한 개의 정렬된 집합으로 만드는 정렬 방법이다. 병합 정렬은 전체 원소들에 대해서 수행하지 않고 부분집합으로 분할(Divide)하고 각 부분집합에 대해서 정렬 작업을 완성(Conquer)한 후에 정렬된 부분집합들을 다시 결합(Combine)하는 분할 정복(Divide and Conquer) 기법을 사용한다.

2개의 정렬된 자료 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 2-way 병합이라 하고, n개의 정렬된 자료 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 n-way병합이라고 한다.

2-way 병합 정렬은 다음과 갑ㅌ으 작업을 반복 수행하면서 완성한다.

1) 분할(Divide) : 자료들을 같은 크기의 부분집합 2개로 분할한다.

2) 정복(Conquer) : 부분집합에 있는 원소들을 정렬한다. 부분집합의 크기가 충분히 작지않으면 순환 호출을 이용하여 다시 분할한다.

3) 결합(Combine) : 정렬된 부분집합들을 하나의 집합으로 결합한다.

시간복잡도 : O(nlog2n)

public class mergeSort {

static int sorted[]=new int[30];

public static void main(String[] args) {

int a[]={69,10,30,2,16,8,31,22};

int size=a.length;

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

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

}

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

mergesort(a,0,size-1);

}

public static void mergesort(int a[], int m, int n)

{

int middle;

if(m<n){

middle=(m+n)/2;

mergesort(a,m,middle);

mergesort(a,middle+1,n);

merge(a,m,middle,n);

}

}

public static void merge(int a[], int m, int middle, int n)

{

int i,j,k,t;

i=m;

j=middle+1;

k=m;

while(i<=middle&&j<=n){

if(a[i]<=a[j]){

sorted[k]=a[i];

i++;

}

else{

sorted[k]=a[j];

j++;

}

k++;

}

if(i>middle) for(t=j ; t<=n ; t++,k++) sorted[k]=a[t];

else for(t=i ; t<=middle ; t++,k++) sorted[k]=a[t];

for(t=m ; t<=n ; t++) a[t]=sorted[t];

for(int l=0  ; l<a.length ; l++){

System.out.print(a[l]+" ");

}

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

}

}

삽입 정렬은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 삽입 정렬에서는 정렬할 자룍 두 개의 부분집합 S와 U로 나뉘어 있다고 가정한다 앞부분 원소부터 정렬을 수행하는데 정렬된 앞부분의 원소들은 부분집합 S가 되고, 아직 정렬되지 않은 나머지 원소들은 부분집합 U가 된다. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하여 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 줄인다. U의 원소를 모두 삽입하여 공집합이 되면 삽입 정렬이 완성된다.

시간복잡도 : 최소 - O(n), 최대 - O(n^2)

public class insertSort {

public static void main(String[] args) {

int a[]={69,10,30,2,16,8,31,22};

int temp,j;

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

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

}

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

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

temp=a[i];

j=i;

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

a[j]=a[j-1];

j=j-1;

}

a[j]=temp;

}

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

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

}

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

}

}

퀵 정렬은 정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준값을 중심으로왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다. 왼쪽 부분집합에는 기준값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준값보다 큰 원소들을 이동시킨다. 이때 사용하는 기준값을 피봇(Pivot)이라고 하는데, 일반적으로 전체 원소 중에서 가운데에 위치한 원소를 피봇으로 선택한다.

퀵정렬은 다음의 2가지 기본 작업을 반복수행하여 완성한다.

1) 분할(Divide) : 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할한다.

2) 정복(Conquer) : 부분집합의 우너소들 중에서 기준값보다 작은 원소들은 왼쪽 부분집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 1이하로 충분히 작지 않으면 순환호출을 이용하여 다시 분할한다.

분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 부분집합과 오른쪽 부분집합을 정렬하는 방법으로 전체 원소들을 정렬한다. 부분집합으로 분할하기 위해서 L과 R을 사용한다.

퀵 정렬을 위한 동작규칙

1. 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피복보다 크거나 같은 원소를 찾아 L로 표시한다.

2. 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시한다. 단, R은 L과 만나면 더 이상 왼쪽으로 이동하지 못하고 멈춘다.

3. 1과 2에서 찾은 L원소와 R원소를 서로 교환한다.

4. L과 R이 같은 원소에서 만나면 피봇과 R의 원소를 서로 교환한다.

5. 3이나 4에서 피봇에 대한 자리 교환이 발생하면, 교환 후의 자리를 피봇의 위치로 확정하고 현재 단계의 퀵 정렬이 끝난다.

6. 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분집합과 오른쪽 부분집합에 대해서 퀵 정렬을 순환적으로 반복 수행하는데, 모든 부분집합의 크기가 1 이하가 되면 퀵 정렬을 종료한다.

시간복작도 : O(nlog2n), 같은 시간 복잡도를 가지는 다른 정렬 방법에 비해 자리교환 횟수를 줄임으로써 실행 시간 성능을 향상시킨 정렬 방법이다.

public class quickSort {

public static void main(String[] args) {

int a[]={69,10,30,16,2,8,31,22};

int size=a.length;

quicksort(a,0,size-1);

}

public static void quicksort(int a[], int begin, int end)

{

if(begin<end){

int p;

p=partition(a,begin,end);

quicksort(a, begin, p-1);

quicksort(a, p+1, end);

}

}

public static int partition(int a[], int begin, int end)

{

int pivot, temp, L, R, t;

L=begin;

R=end;

pivot=(begin+end)/2;

while(L<R){

while((a[L]<a[pivot])&&(L<R)) L++;

while((a[R]>=a[pivot])&&(L<R)) R--;

temp=a[L];

a[L]=a[R];

a[R]=temp;

if(L==pivot){

for(int i=0 ; i<a.length ; i++) System.out.print(a[i]+" ");

System.out.println();

return R;

}

}

temp=a[pivot];

a[pivot]=a[R];

a[R]=temp;

for(int i=0 ; i<a.length ; i++) System.out.print(a[i]+" ");

System.out.println();

return R;

}

}

버블 정렬은 인접한 두개의 원소를 비교하여 자리를 교환하는 방식으로, 첫 번째 원소부터 마지막 원소까지 반복하면 가장 큰 원소가 마지막 자리에 온다. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 해서 버블 정렬이라고 한다.

시간복잡도 : O(n^2)

public class bubbleSort {

public static void main(String[] args) {

int a[]={69,10,30,2,16,8,31,22, 18};

int temp;

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

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

}

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

for(int i=a.length-1 ; i>=0 ; i--){

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

if(a[j-1]>a[j]){

temp=a[j-1];

a[j-1]=a[j];

a[j]=temp;

}

}

}

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

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

}

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

}

}

선택 정렬은 전체원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다. 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환한다. 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환하고, 그 다음에는 세 번째로 작은 원소를 찾아서 세 번쨰 원소와 자리를 교환한다. 과정을 반복하면서 정렬을 완성한다.

시간복잡도 O(n^2)

public class selectionSort {

public static void main(String[] args) {

int a[]={69,10,30,2,16,8,31,22};

int min,temp;

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

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

}

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

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

min=i;

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

if(a[j]<a[min]) min=j;

}

temp=a[i];

a[i]=a[min];

a[min]=temp;

}

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

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

}

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

}

}

컴퓨터에서 수행되는 정렬은 컴퓨터 메모리 내요에서 정렬하는 내부 정렬(Internal Sort)과 메모리의 외부인 보조 기억 장치에서 정렬하는 외부 정렬(External Sort)로 분류할 수 있다.

내부정렬

내무정렬은 정렬할 자료를 메인 메모리에 올랴서 정렬하는 방식으로, 정렬 속도는 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한된다.

교환방식 : 키를 비교하교 교환하여 정렬하는 방식(선택정렬, 버블정렬, 퀵정렬)

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

병합방식 : 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)

분배방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수 정렬)

선택방식 : 이진 트리를 사용하여 정렬하는 방식(히트 정렬, 트리 정렬)

외부정렬

외부정렬은 대용량의 보조 기억 장치를 사용하기 떄문에 내부 정렬보다 속도는 떨어지지만, 내부 정렬로 처리할 수 없는 대용량의 자료를 정렬할 수 있다.