버블 정렬, 선택 정렬, 피보나치 수열

버블 정렬

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

 for(i=n-1; i>0; i--){
    // 0 ~ (i-1)까지 반복
    for(j=0; j<i; j++){
      // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
      if(list[j]<list[j+1]){
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }

 

버블 정렬 알고리즘 특징

💡 장점

구현이 매우 간단함

 

💡 단점

순서에 맞지 않는 요소를 인접한 요소와 교환

하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 함

특히 특정 요소가 최종 정렬의 위치에 이미 있는 경우라도 교환이 일어남

일반적으로 자료의 교환 작업(swap)이 자료의 이동 작업(move)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않음

---

선택 정렬

☝ 제자리 정렬 알고리즘의 하나

   입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

✌ 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

   첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣음

   두 번째 순서에는 두 번째 위치에 남은 값 중에서 최솟값을 넣음

👌 과정 설명

   주어진 배열 중 최솟값을 찾음

   그 값을 맨 앞에 위치한 값과 교체

   맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체

   하나의 원소만 남을 때까지 위의 1~3 과정을 반복

int indexMin, temp; 
for (int i = 0; i < arr.length-1; i++) { // 1. 
	indexMin = i; 
	for (int j = i + 1; j < arr.length; j++) { // 2. 
		if (arr[j] < arr[indexMin]) { // 3. 
			indexMin = j; 
		} 
	} 
	// 4. swap(arr[indexMin], arr[i]) 
	temp = arr[indexMin]; 
	arr[indexMin] = arr[i]; 
	arr[i] = temp; 
} 
System.out.println(Arrays.toString(arr));

 

선택 정렬의 특징

💡 장점

버블 정렬과 마찬가지로 알고리즘이 단순함

정렬을 위한 비교 횟수는 많지만, 버블 정렬에 비해 실제 교환하는 횟수는 적기때문에 많은 교환이 일어날때 비교적 효율적임

 

 

💡 단점

시간 복잡도가 n^2로 비효율적임

불안정 정렬임

---

피보나치 수열

피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 됨

👉 입력받은 수 만큼 피보나치 수열 구하기

import java.util.Scanner;
public class Pibo {
          Scanner s = new Scanner(System.in);
          System.out.print("정수 입력 : ");
          int j=s.nextInt();
          
          int num1,num2,sum;
          num1=0; 
          num2=1; 
          sum=1; // 첫번째 1은 그냥 초기값으로 설정
          
          for(int i=0; i<j; i++)
          {
              System.out.print(sum+" ");
              sum=num1+num2; 
              num1=num2;
              num2=sum; 
          }
     }
}

✔ 실행 결과

   정수 입력 : 10
   1 1 2 3 5 8 13 21 34 55