개발자의 개발 블로그

선택 정렬은 오히려 버블 정렬보다도 쉽고 간단한 알고리즘이다. 

1. 주어진 리스트 중에 최소값을 찾은 후, 

2. 그 값을 리스트 맨 앞에 위치한 값과 교체(교환)한다.

3. 맨 처음 위치를 제외하고(이미 최소값이므로) 나머지 리스트를 같은 방법으로 반복한다.

딱, 세가지만 생각하면 된다. 

① 주어진 리스트 중에 최소값을 찾는 방법

위와같은 배열a[]가 존재할 때, 리스트 중 가장 작은 요소의 인덱스값을 구하기 위해서는 어떻게 할까?

int[] arr = {3,5,1,7,9,2,6};

int min_index = 0;

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

if(arr[min_index]>arr[i]) min_index = i;

System.out.println(arr[min_index] +" "+arr[i]);

}

요런식으로 하면 인덱스 0(값6)이후의 값부터 비교해가며 최소값의 인덱스를 찾을 수 있다. 

min_index = 2일 것이다.

② 리스트 맨 앞 요소와 위치를 교환한다.

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

if(arr[min_index]>arr[i]) min_index = i;

System.out.println(arr[min_index] +" "+arr[i]);

//아래 부분이 추가됨.

temp = arr[0];

arr[0] = arr[min_index];

arr[min_index]= temp;

}

이러면 될까? 되긴 한다. 그렇지만 어떻게 나올까? 

1 5 3 7 9 2 6 

뭐야 이게? 뭐가 되긴 됐는데? 그렇다. 최소값 1이 맨 앞 3과 자리가 바꼈다....

근데. ㅡ_ㅡ;;;다른건 움직이지 않았다. 위 그림에서 보면 두번째 그림과 같다는 것을 알수 있다.

그래서 우리는 반복을 해주어 계속 정렬을 해야한다.

③ 리스트 맨 앞 요소를 제외한 리스트 전체를 위 과정을 반복실행 한다.

맨 앞 즉, 0번째 인덱스 정렬은. 끝났다. 1번째 인덱스부터 새롭게 시작한다. 그러면

min_index값은 어떻게 될까? 당연히.. 1부터다. 

즉, (배열의 크기-1)만큼 돌려야 모든 요소들이 비교를 해가면서 정렬이 완성될 것이다.(그림 참조)

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

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

if(arr[min_index]>arr[j]) min_index = j;

temp = arr[i];

arr[i] = arr[min_index];

arr[min_index]= temp;

}

}

일단, ②에 나오는 for문을 감싸는 for문을 하나 더 삽입해서 이중for문이 되도록 해야 한다.

기존에 i변수를 j로 바꾸고 0번째 인덱스를 의미하는 0을 지우고 j를 넣는다.

왜냐하면 j가 하나하나 증가되면서 값을 저장하기 때문이다. 따라서,다음과 같이 정렬이 된다.

1 2 3 5 6 7 9 

선택 정렬의 성능평가 

버블 정렬과 성능상 큰 차이가 없다. 선택 정렬의 빅-오 역시 O(n^2) 

이 둘을 비교하는 것은 도토리 키재기..라고 할 수 있다.

버블 정렬은 정렬하면 가장 먼저 떠오르는 간단한 정렬방법이다.

버블 정렬은 이름 그대로 앞에서부터 순서대로 비교하고 교환하는 과정이 마치 거품이 일어나는 모습에

비유되어 버블 정렬이라는 이름이 지어진 것이다.

그만큼 이해하기도, 구현하기도 쉽고 간단하다. 물론 구현이 쉬운만큼 성능적으로는 매우 떨어진다.

만약, 오름차순으로 정렬을 하려고 한다. 아래와 같은  배열 6 1 2 3 4 5이 있다면, 

위 그림에서 보듯, 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.

두 개의 데이터를 비교하여, 정렬순서상 위치가 바뀌어야 할 경우에는 두 데이터의 위치를 바꿔나간다.

즉, 정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보내는 것을 반복하는게 바로 이 정렬의 핵심이다.

위 사진의 경우에는 6만 보내면 해결됐지만, 만약 6 5 4 3 2 1이라면 모든 값을 비교 후 이동함으로 최악이다.

먼저, 하나의 요소와 그 뒷 요소를 비교해서 앞이 뒤보다 크다면 앞.뒤의 위치를 변경하는 코드를 구현하면,

import java.util.Scanner;

public class Main {
 public static void main(String[] args) {

  int bubbleSort[] = {6,3,4,5,2,1};

  for (int i = 0; i < bubbleSort.length; i++) {
   System.out.print (bubbleSort[i]+" ");
  }  // 6 3 4 5 2 1 출력
  

BubbleSort(bubbleSort,bubbleSort.length); 

  System.out.println();
  for (int i = 0; i < bubbleSort.length; i++) {
   System.out.print (bubbleSort[i]+" ");
  }  // 1 2 3 4 5 6 출력
 }

 private static void BubbleSort(int[] bubbleSort, int length) {
  
  int temp;
  
  for (int i = 0; i < length-1; i++) {
   for (int j = 0; j < (length-i)-1; j++) {
    if(bubbleSort[j] > bubbleSort[j+1]){
         temp = bubbleSort[j];
         bubbleSort[j] = bubbleSort[j+1];
         bubbleSort[j+1] = temp;
    }
   }
  }
 }
}

위에서 BubbleSort()메소드가 바로 버블 정렬 알고리즘을 구현한 코드이다.

++추가적으로 다른 방법으로 버블 정렬을 구현하였다. 이것이 더욱 간단하지 않을까싶다.

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int num1 = scanner.nextInt();

int[] arr = new int[num1];

int flag = 0, temp = 0;

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

arr[i] = scanner.nextInt();

}

for (int i = num1 - 2; i >= 0; i--) {

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

if (arr[j] > arr[j + 1]) {

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

for (int j = 0; j < arr.length; j++) {

System.out.print(arr[j]);

}

}

}

입력 :

7

2 5 11 24 8 1 9

출력 :

1 2 5 8 9 11 24 

성능

정렬 알고리즘의 성능은 두 가지를 근거로 판단한다.  

1. 비교 횟수  : 두 데이터간의 비교연산의 횟수

2. 이동 횟수  : 위치의 변경을 위한 데이터의 이동 횟수.

최선의 경우는 배열이 이미 완벽하게 정렬되어 있는 상태 - 데이터의 이동이 한 번도 일어나지 않음

최악의 경우에는 내림차순.. 즉, 역순으로 정렬되어 있을 경우 비교횟수 = 이동횟수.. 

버블 정렬은 빅오 오브 n^2 (= O(n^2))이므로 매우 좋지 않은, 실제로 사용하지 부담스러운 성능을 보인다.

하지만, 코드가 간단하게 구현할 수 있기 때문에 간단한 배열의 정렬의 경우에는 이 방식을 사용해도 무방하다..

이상으로 버블 정렬에 대한 정리를 마치도록 하겠다. 다음번에는 선택 정렬!!!

1. 배열(Array)

[배열(Array)이란 무엇인가]

- 거의 모든 언어에서 지원하는 문법이다.

- 배열은 가장 기본적인 자료구조다. 즉, 앞으로 배울 많은 자료구조들이 배열을 부품으로 사용된다.

- 데이터가 적다면 물론 일반 변수를 사용하여 값을 저장하여 사용하면 문제없다.

- 하지만, 데이터가 많아질수록 그룹 관리에 대한 필요성이 생긴다. 이럴 때 배열을 사용하게 된다.

- 즉, 배열은 여러 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 목적으로 사용하는 자료구조이다.

- element = value + index (value = 저장된 실제 데이터, index는 데이터를 저장 및 조회를 위한 위치 식별자(Index))

- 배열은 반복문과 조합하면 훨씬 더 효율적으로 사용할 수 있다. 

[배열의 생성 방법]

int[] number = new int[5];

number[0] = 10;

number[1] = 20;

number[2] = 30;

number[3] = 40;

number[4] = 50;

위 코드가 바로 배열을 생성하고, 인덱스에 값을 대입하는 코드이다. 또한 더 간단하게 생성을 하고 싶다면 

int[] number2 = {10,20,30,40,50};

또는 int[] number3 = new int[]{10,20,30,40,50};

모두 같은 의미이다.

[배열 안에 저장된 값을 가져오는 방법(하나의 데이터를 가져올때)]

이를 위해서 인덱스(Index)가 필요하다. 

number[0];   을 호출하면 0번째 인덱스의 값(value)를 가져오게 된다

[배열 안에 저장된 값을 가져오는 방법(하나의 데이터를 가져올때)]

이를 위해서 반복문이 필요하다. while 또는 for문을 통해 0부터 0!부!터! 배열의 크기만큼(number.length) 반복한다.

[배열 안에 저장된 길이를 구하는 방법]

[ArrayList 사용방법 - 추가(Insert)]

number.add(10);

number.add(20);

number.add(30);

number.add(10);