개발자의 개발 블로그

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

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) 

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

이게 정말 열받는다!! 스페이스로 인위적으로 맞춰보려했으나. 아무리해도 실패!!

찾아보니 씨언어와 같이 해주면 된다고 하더라.

%5d : 정수를 전체 자릿수 5자리로 오른쪽 정렬로 출력하라.

코드 

System.out.printf("%5d  PERFECT",number);

이렇게 하면 

요렇게 잘 정렬되어 나오게 된다...

예를들어 4를 입력받으면 1 2 4가 출력되고, 6을 입력받으면 1 2 3 6이 나오도록 코드를 짜보자.

약수란, 나누어 떨어지는 것을 의미하므로 코드상으로 아래와 같이 작성하면 결과가 출력된다.

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int number = scanner.nextInt();

if (number <= 10000) {

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

if(number%j==0)

System.out.println(j+" ");

}

}

}

}

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

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

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

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

만약, 오름차순으로 정렬을 하려고 한다. 아래와 같은  배열 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);

C언어에서 포인터를 잘 이해하기 위해서는 메모리 공간에 대한 그림을 잘 그리는 것이 중요하다.

또한, C언어에서는 시작번지만을 가지고 위치를 표현한다.

자료형 int num = 7; 의 위치가 어디냐?

라는 질문을 했을 때, 4바이트이므로 어디부터 어디까지입니다. 라는 대답을 할 수 있다.

하지만, 시작번지를 알면 int형이 4바이트임을 알고 있으므로 끝은 쉽게 계산할 수 있기 때문이다.

이 시작번지가 바로 주소값이며 이 역시 정수이다. 따라서, 이것 역시 저장 가능하며 이를 저장하기 위한 변수가

바로 포인터 변수이다.

즉, 포인터 변수는 어떤 변수에 대한 메모리에 할당된 주소값을 저장하기 위한 변수이다.   

int num = 7;          // 일반적인 변수 선언

int *ptr = &num;    // 포인터 변수 선언 후 num의 주소값을 포인터 변수 ptr에 저장

ptr는 포인터 변수명이며, int *는 int형 변수의 주소값을 저장하겠다는 의미의 포인터 변수의 선언이다.

&연산자 : 주소값을 가져오는 연산자이므로. 즉 ptr = &num의 경우 num의 주소값을 ptr변수에 저장한다.

그리고 이러한 것을 포인터 변수 ptr이 int형 변수 num을 가리킨다.  라고 표현한다.

말그대로, 포인터 변수 ptr에는 변수 num의 주소값이 들어있고, 아래 그림과 같이 가리키고 있다. 

-

[포인터 변수 선언하기~!]

포인터 변수는 가리키고자 하는 변수의 자료형에 따라서 선언하는 방법이 달라진다.

• int형 변수를 가리키는 포인터 변수의 자료형은 int

• double형 변수를 가리키는 포인터 변수의 자료형은 double

• char형 변수를 가리키는 포인터 변수의 자료형은 char

아래와 같은 변수의 자료형에 맞지 않는 포인터 변수의 선언은 문제가 발생할 수 있다.

int main(void) {

double number = 10.123;

int * ptr = &number;

printf("%d", *ptr);

}

컴파일 에러는 발생하지 않지만, 많은 문제를 일으킬 수 있다.

다양한 포인터 형이 존재하는 이유는 메모리 공간을 참조하는 기준이 된다.

즉, 포인터 형의 정의는 *연산자를 통핸 메모리 공간의 접근 기준을 마련하기 위해서이다.

위에 같은 코드에서는 변수는 double형 8바이트이지만, int *이므로 ptr 포인터변수는

intg형이므로 4바이트의 값을 구하게 되고 결국은 쓰레기값이 생성되므로 무의미하다. 

[포인터와 관련이 있는 연산자들~!]

&연산자 : 변수의 주소값을 반환하는 연산자.

- 피연산자의 주소값을 반환하는 연산자이다.

 - &num 과 같이 우측에 변수가 와야하고, 상수가 올 수 없다.

*연산자 : 포인터가 가리키는 메모리를 참조하는 연산자.

- 포인터가 가리키는 메모리 공간에 접근할 때 사용하는 연산자이다.

- 여태껏 포인터 변수에 주소값을 저장만 했고, 사용하지 않았다. 사용하지 않을거면 왜 포인터변수를 만드나?

바로 이 연산자를 이용하여 포인터 변수가 가리키는 메모리 공간인 변수에 접근하여 값을 조작할 수 있다.

다음과 같이 사용이 가능하다.

int main(void) {

int num = 20;

int * pnum = &num;

*pnum += 50;                    // pnum  = pnum + 50

printf("%d", *pnum);        

}

결과는 : 70

[잘못된 포인터의 사용과 널 포인터의 사용]

포인터 변수에는 메모리 주소값이 저장되고, 이를 이용하여 해당 메모리 공간에 접근도 가능하기 때문에

상당히 주의를 기울여야 한다.

1. 포인터 주소값을 넣지 않을 때.

int * ptr;        // 주소값을 저장하지 않았다!!!!

ptr = 500;      // 그리고 500을 대입하였다!!!!

이럴 경우. 쓰레기값이 삽입된다. 그런데 그 쓰레기값이 하필 OS에서 중요한 메모리 공간이었다면?

치명적인 문제가 발생할 수도 있다. 요즘은 컴퓨터가 많이 좋아져서 자동적으로 프로그램을 중지시켜

메모리에 접근을 방지한다고 한다.

하지만, 이렇게 쓰게 되면 쓰나마나.

2. 변수의 주소값을 이상하게 넣었을때.

int * ptr = 255;  // 주소값이 255가 어디여???

ptr = 500;      // 그리고 500을 대입하였다!!!!

255가 어딘줄 알고 저장을 해? 이것 역시 쓰레기값이다.

3. 포인터 변수 초기화 시키는 방법 -> NULL

포인터 변수를 먼저 선언해놓은 뒤, 나중에 사용하고자 한다면 0 또는 NULL로 초기화를 해준다.

int *ptr1 = 0;

int *ptr2= NULL;

0을 널 포인터라고 하며, 0은 0번지가 아니라 아무것도 가리키지 않는다는 의미이다.

NULL 역시 이는 실제로 상수 0으로 정의되어 있다.