정렬(sort)

정렬

selection sort(선택 정렬)

1.가장큰값을찾는다.

2.맨끝의 자리와 바꾼다.

3.똑같은일은 나머지 데이터와 반복한다.

시간복잡도 O(n^2)

for last<- n downto 2

    A[1...last] 중 가장 큰수 A[k]를 찾는다.

    A[k] <-> A[last]  A[k]와 A[last]의 값을 교환

import java.util.*;
 
 
public class Solution {
 
    public static void selectSort(int[] arr){
        int min_index; //최소값 인덱스
        int temp;      //바꿀 값 저장될 변수
        
        if(arr == null || arr.length <= 1) //배열의 값이 없거나 길이가 1보다 작거나 같은때
            return;
        
        for(int i=0; i<arr.length-1; i++){ //최소값을 찾기 위해 마지막 배열 앞까지 반복
            
            min_index = i;
            for(int j=i+1; j<arr.length; j++){ //i보다 큰 인덱스 중
                if(arr[j]<arr[min_index]) //배열의 값중 작은 인덱스를 min_index에 저장
                    min_index = j;
            }//최종적으로 최소값이 min_index에 저장 된다.
            temp = arr[i]; //최소값하고 현재값하고 위치 변경
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }
        
        
        
    }
    public static void main(String args[]){
 
        Scanner sc = new Scanner(System.in);
         
 
        int[] arr = {3,10,7,66,24};
        
        selectSort(arr);
        
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        
       
    }
    
   
   
}
 
 

Bubble sort(버블 정렬)

: 두 인접한 원소를 검사하여 정렬하는 방법

- 인접해 있는 두개의 값을 비교해서 자료 교환

시간복잡도 O(n^2)

코드가 단순

7 4 11 9 2

4 7 11 9 2

4 7 11 9 2

4 7 11 9 2

4 7 9 11 2

4 7 9 2 11

4 7 9 2 11

4 7 9 2 11

4 7 2 9 11

4 7 2 9 11

4 2 7 9 11

2 4 7 9 11

for last<- n downto 2

for i <- 1 to last-1

if(A[i]>A[i+1]) then A[i]<-> A[i+1] 교환

import java.util.*;
 
 
public class Solution {
 
    public static void bubbleSort(int[] arr){
        int temp;
        
        if(arr == null || arr.length == 0)
            return;
        
        for(int i=0; i<arr.length; i++){
            for(int j=0; j<arr.length-1; j++){
                if(arr[j]>arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        
        
    }
    public static void main(String args[]){
 
        Scanner sc = new Scanner(System.in);
         
 
        int[] arr = {3,10,7,66,24};
        
        bubbleSort(arr);
        
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        
       
    }
    
   
   
}
 
 

Insertion sort(삽입 정렬)

: 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여, 자신의 위치를 찾아 삽입

최선의 경우 O(n)

최악 시간복잡도 O(n^2)

public class Main {
    public static void main (String[] args) {
        int[] a = {5,2,4,6,1,3};
        
        for(int j = 1; j < a.length; j++) {
            int key = a[j];
            int i = j-1;
 
            while(i >= 0 && a[i] > key) {
                a[i+1]=a[i];
                i = i - 1;
            }
            a[i+1]=key;
        }
        
        for(int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}
 
 

merge sort(합병정렬)

분할정복법

1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

2. 정복 : 각각의 작은 문제를 순환적으로 해결

3. 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

합병할때는 정렬하면서 합친다.

[5 6] [1 3] [7 8] [2 4]

[1 3 5 6] [2 4 7 8]

[1 2 3 4 5 6 7 8]

시간복잡도 O(NlogN)

mergeSort(A[], p, r)  -> A[p....r]을 정렬한다.

{

if(p<r) then{

q<-(p+q)/2;              //p,q의 중간 지점 계싼

mergeSort(A,p,q); //전반부정렬

mergeSort(A,q+1,r); //후반부정렬

merge(A,p,q,r); //합병

}

}

merge(A[],p,q,r)

{

정렬되어 있는 두 배열 A[p....q]와 A[q+1...r]을 합하여

정렬된 하나의 배열 A[p...r]을 만든다.

}

merge는 기본적으로 recursion을 가지고 있고 문제점은 배열이 하나더 필요하다.

import java.util.*;
 
 
public class Solution {
    
    
    public static void mergeSort(int[] arr, int left, int right){
        if(left < right){
            int middle = (left+right)/2; //중간지점 
            
            mergeSort(arr,left,middle); //left부터 중간지점까지 재귀
            mergeSort(arr,middle+1,right); //중간지점+1부터 right까지 재귀
            merge(arr,left,middle,right); //합병
        }
    }
    
    public static void merge(int[] arr, int left, int middle, int right){
        
        int i = left; 
        int j = middle+1;
        int k = left;
        int temp[] = new int[arr.length];
        
        while(i<=middle && j<=right){ //i가 middle보다 작거나 같고 j가 right보다 작거나 같을때
            if(arr[i] <= arr[j]) //j 배열의 값이 i 배열의 값보다 크다면
                temp[k++] = arr[i++]; //temp배열에 arr[i] 저장하고 한 인덱스씩 증가
            else
                temp[k++] = arr[j++];
        }
        while(i<=middle) //middle 왼쪽에 남아있는 값들
            temp[k++] = arr[i++];
        while(j<=right) //middle 오른쪽에 남아있는 값들
            temp[k++] = arr[j++];
        for(i=left;i<=right;i++)
            arr[i] = temp[i];
        
    }
    
    public static void main(String args[]){
 
        Scanner sc = new Scanner(System.in);
         
 
        int[] arr = {3,10,7,66,24};
        
        mergeSort(arr,0,arr.length-1);
        
   
        System.out.println(Arrays.toString(arr));
      
        
       
    }
    
   
   
}
 
 

quick sort(빠른정렬)

분할정복법

분할 : 배열을 다음과 같은 조건이 만족되도록 두 부분으로 나눈다.

 elements in lower parts <= elements in upper parts

정복: 각 부분을 순환적으로 정렬한다.

합병: nothing to do

1.정렬한 배열이 주어짐, 마지막 수를 기준(pivot)으로 삼는다.

2.기준보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치(분할)한다.

3.기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다.

1. 배열의 원소중 기준점(pivot)을 선택한다.

2. 선택된 pivot 기준으로 더 작은값은 왼쪽으로 더 큰값은 오른쪽으로 옮긴다.

3. pivot 기준으로 좌우 부분 배열에 대해서 1번부터 다시 수행한다.

4. 원소가 하나 뿐인 배열은 더 이상 수행하지 않는다.

5. 모든 값이 피벗으로 선정된 적이 있으면 정렬 종료

6. 최종적으로 모든 값들이 한번 씩 피벗으로 선정되며 자신의 자리를 찾아간다.

최악의 경우 O(n^2)

평균 O(nlogN)

quickSort(A[],p,r)

{

if(p<r) then{

q=partition(A,p,r);

quickSort(A,p,q-1);

quickSort(A,q+1,r);

}

}

partition(A[],p,r)

배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고

A[r]이 자리한 위치를 retrun 한다.

if A[j]>=x

j<-j+1;

import java.util.*;
 
 
public class Solution {
    
    public static int partition(int[] arr, int left, int right){
        // 값을 비교하고 로우와 하이를 이동시키면서 값의 교환이 이루어지는 함수
 
        int pivot = arr[(left+right)/2];
        
        while(left<right){
            while( (arr[left] < pivot) && (left < right) )
                left++;
            while( (arr[right] > pivot) && (left < right) )
                right--;
            if(left<right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        return left;
    }
    
    public static void quickSort(int[] arr, int left, int right){
        if(left<right){
            int new_pivot = partition(arr,left,right);
            
            quickSort(arr,left,new_pivot-1);
            quickSort(arr,new_pivot+1,right);
            
            
        }
    }
    
    
    public static void main(String args[]){
 
        Scanner sc = new Scanner(System.in);
         
 
        int[] arr = {3,10,7,66,24};
        
        quickSort(arr,0,arr.length-1);
        
   
        System.out.println(Arrays.toString(arr));
      
        
       
    }
    
   
   
}
 
 

Heap Sort(힙 정렬)

heap은 complete binary tree이면서 heap property를 만족해야한다.

max heap property : 부모는 자식보다 크거나 같다.

or

min heap property : 부모는 자식보다 작거나 같다. 

힙은 일차원 배열로 표현 가능 : A[1...n]

루트노드 A[1]

A[i]의 부모 = A[i/2];

A[i]의 왼쪽 자식 = A[2i];

A[i]의 오른쪽 자식 = A[2i+1];

MAX-HEAPIFY : root만 heap property 만족하지않음

해결..

1. 두자식들 중 더 큰쪽이 나보다 크면 exchange한다.

2. 두자식들 중 더 큰쪽이 나보다 크면 exchange한다.

 heapsort

1.주어진 데이터로 힙을 만든다.

2.힙에서 최대값(루트)를 가장 마지막 값과 바꾼다.

3.힙의크기가 1 줄어든 것으로 간주한다. 즉 , 가장 마지막값은 힙의 일부가 아닌 것으로 간주한다.

4.루트노드에 대해서 HEAPIFY(1)한다.

5.2~4번 반복한다..

힙의 응용: 우선순위 큐

최대 우선순위 큐

-INSERT(x) : 새로운 원소 x를 삽입

-EXTRACT_MAX() : 최대값을 삭제하고 반환

최소 우선순위 큐

MAX-HEAP-INSERT(A,key){

heap_size = heap_size+1;

A[heap_size] = key;  //마지막자리에 힙 추가

i = heap_size;       //i는 문제아노드

while(i>1 and A[PARENT(i)] < A[i]){    //i>1:루트노드가 아니고 문제아노드에 저장된 값이 부모노드의저장된값보다 크면

exchange A[i] and A[PARENT(i)];

i=PARENT(i);

}

EXTRACT_MAX()

if heap-size[A]<1

then error "heap underflow"

max<-A[1]

A[1]<-A[heap-size[A]]

heap-size[A] <- heap-size[A] -1

MAX-HEAPIFT(A,1)

return max

Comparison Sort

-데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘

-따라서 데이터들간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능(문자열,알파벳,사용자정의 객체등)

-버블소트,삽입정렬,합병정렬,퀵소트,힙정렬 등

Non-Comparison Sort

-정렬할 데이터에 대한 사전지식을 이용 - 적용에 제한

-Bucket sort

-Radix sort

정렬문제의 하한

하한(lower bound)

-입력된 데이터를 한번씩 다 보기위해서 최소 o(n)의 시간복잡도 필요

-합병정렬과 힙정렬 알고리즘들의 시간복잡도는 o(nlog2n)

-어떤 comparison sort알고리즘도 o(nlon2n)보다 나을수 없다.

선형시간 알고리즘(sorting in linear time)

counting sort

-n개의 정수를 정렬하라. 단 모든 정수는 o에서 k사이의 정수이다.

Radix sort

-n개의 d자리 정수들 가정

-가장 낮은 자리수부터 정렬

*stable sort란? 값이 같다면 입력에서 들어온 순서대로

Sorting in Java

<기본 타입 데이터의 정렬>

-Arrays 클래스가 primitive 타입 데이터를 위한 정렬메서드를 제공

ex)

int [] data = new int [capacity];

Arrays.sort(data);

Arrays.sort(data,0,size); //데이터의 개수가 정해져있다.

-int 이외의 다른 primitive 타입 데이터(double,char등)에 대해서도 제공

<객체의 정렬 : 문자열> //문자열은 사전식순서로 정렬

String [] fruits = new String [] { "pineapple","apple","orange","banana"};

Arrays.sort(fruits);

for(String name:fruits)

System.out.println(name);

-ArrayList 정렬 : 문자열

List<String> fruits = new ArrayList<String>();

Collections.sort(fruits);

배열일떈 Arrays.sort

리스트일때 Collections.sort

-사용자정의객체

객체의정렬 : Comparable Interface

두가지 기준을 동시에 지원하려면?

-하나의 객체 타입에 대해서 2가지 이상이 기준으로 정렬을 지원하려면 Comparator를 사용