선택 정렬

김근범·2022년 7월 17일
1

알고리즘

목록 보기
3/11

정렬

  • 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 알고리즘
  • 종류
    -버블정렬
    -선택정렬
    -삽입정렬
    -병합정렬
    -퀵정렬
    -힙정렬
    -트리정렬
    등...

선택 정렬

  • 선택 정렬은 앞쪽부터 정렬하는 방식.
  • 주어진 데이터를 기준으로 사용자가 정한 기준에 맞는 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬.
  • 데이터에서 최소값을 찾아야 하기 때문에 비교 횟수는 많지만 실제로 값을 바꾸는 교환 횟수가 적다는 것이 특징.
  • 시간복잡도 : O(n^2)

장점

  • 알고리즘이 비교적 단순하다.
  • 대부분의 데이터가 이미 정렬되어 있는 경우 효율적이다.
  • 안정 정렬

단점

  • 평균과 최악의 시간복잡도가 O(n^2)
  • 배열의 길이가 길어질 수록 비효율적이다.

Pseudo Code

for i=1 to data 개수 do
	for j = i to data 개수 do
    	if min > data[j] then
        	min -> data[j]
            index = j
   	swap data[i], data[j]

예시

3 5 7 2 4 1 9 8 6 10 정렬

public class SelectionSort {
	public static void main(String []args) {
		int i, j, min, temp, index=0;
		int[] array = {3, 5, 7, 2, 4, 1, 9, 8, 6, 10};
		for(i =0 ; i < array.length; i++) {
			min = 9999;
			for(j = i; j < array.length; j++) {
				if(min > array[j]) {
					min = array[j];
					index = j;	
				}
			}
			temp = array[i];
			array[i] = array[index];
			array[index] = temp;
		}
		
		for(i=0;i<array.length;i++) {
			System.out.print(array[i] + " ");	
		}
		System.out.println();
	}
}

이미지 출처 : https://github.com/GimunLee/tech-refrigerator/

1개의 댓글

comment-user-thumbnail
2022년 7월 18일

선택 정렬 헷갈렸는데 잘 보고 갑니다 o( ̄▽ ̄)d !!

답글 달기