[알고리즘] 2주차: 04. 정렬1

04. 정렬1

• 선택정렬 : \(\Theta (n^2)\)
  • 배열에서 가장 큰 원소를 찾아 맨 뒤로 이동
  • 맨 뒤의 원소는 가장 큰 원소로 채워지니까 더이상 신경쓰지 않는다
  • 맨 뒤에서 하나씩 앞으로 이동하면서 동일 작업 반복

  //간결 명확 표현
  selectionSort(A[], n){
  	for last <- n downto 2{ //n-1회 반복
  		A[1 ... last] 중 가장 큰 수 A[k]를 찾는다; //비교 횟수, n^2에 비례
  		A[k] <-> A[last]; //A[k]와 A[last]의 값을 swap 
  	}
  }
  

  //자세한 표현
  SelectionSort(A[], n){
  	for last <- n downto 2 {
  		k <- theLargest(A, last);
  		A[k] <-> A[last];
  	}
  }
  
  theLargest(A[], last){
  	largest <- 1;
  	for i <- 2 to last {
  		if (A[i] > A[largest]) then largest <-i;
  	}
  }
  

  • 부분 배열(n의 크기에 따라 변화)의 크기만큼 반복

 

• 버블 정렬 : \(\Theta (n^2)\)
  • 배열에서 가장 큰 원소를 찾아 맨 뒤로 이동 (선택정렬과 같음)
  • 제일 큰 원소를 옮기는 방법이 다름 : 이웃한 숫자를 비교하며 순서가 제대로 되어있지 않으면 바로바로 바꾸면서 진행

  //
  bubbleSort(A[], n){
  	for last <- n downto 2{ //n-1회
  		for i <- 1 to last-1{ //last-1 회,  선택정렬과 비교횟수 동일
  			if(A[i]>A[i+1]) then A[i] <-> A[i-1];
  		}
  	}
  }
  

 

• 삽입정렬 : 최악의 경우 - \(\Theta (n^2)\) , 절반 정도라고 해도 여전히 \(\Theta (n^2)\) , 완전 정렬 되어있으면 : \(\Theta (n)\)
  • 이미 정렬된 크기 i 배열에 하나의 원소를 더 더해 정렬된 크기 i+1 배열을 만드는 과정을 반복
  • 선택, 버블정렬은 크기 n 배열에서 시작해 크기를 하나씩 줄여나감
  • 삽입정렬은 크기 1에서 시작해 한번 반복할 때마다 정렬된 배열의 크기를 하나씩 늘려나가는 방식

  //
  insertionSort(A[], n){
  	for i <- 2 to n{ //A[1] ~ A[i-1]은 정렬이 완료
  		A[1 ... i]의 적당한 자리에 A[i]를 삽입; //삽입하면 A[i]까지 정렬 완료, 삽입과정은 적당한 위치를 찾을 때까지 반복
  	}
  }
  

 

 

[문제]

1. ( 삽입 )정렬은 비효율적인 정렬 알고리즘에 속하지만 배열이 거의 정렬되어 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이다. 이 정렬 알고리즘은?

        배열이 거의 정렬되어 있다면, 삽입하기 위해 반복해야 하는 부분이 매우 적어져 거의 상수의 시간이 소요된다.

 

 

출처

K-MOOC : 선복근 교수님 - 알고리즘

http://www.kmooc.kr/courses/course-v1:HOSEO+HOSEOSW01+2021_12/about