알고리즘과 선택정렬 , swap함수

알고리즘(Algorithm)

- 문제를 해결하기 위한 일련의 명령어들의 집합으로, 특정한 일을 수행하거나 문제를 해결하는데 사용되는 절차나 방법이다.

 

- 조건

• 입력:(외부)원인>= 0 -> 알고리즘은 0개 이상의 입력을 받아야한다. 이 입력은 외부에서 제공되며, 알고리즘의 작동을 위한 원인이 된다. 
• 출력: 결과>=1 -> 알고리즘은 1개 이상의 출력을 생성해야한다. -> 이 출력은 알고리즘의 수행결과 이다.
• 명백성: 모호하지 않은 명확한 명령 -> 알고리즘의 각 단계는 모호하지않고 명확해야한다. 즉, 각 단계는 정확하게 어떻게 수행되는지 명시해야한다.
• 유한성 :종료 -> 알고리즘은 유한한 단계 후에 종류되어야 한다. 무한 루프에 빠지지않도록 설게해야한다. 
• 유효성: 기본적,실행가능명령 -> 알고리즘의 각 단계는 실행 가능해야하며, 모든 입력에 대해 올바른 출력을 생성해야한다.
• program = algorithm : 프로그램은 알고리즘을 구현하는것이다. 즉, 알고리즘은 문제 해결의 절차나 방법을 나타내며, 프로그램은 이를 실제로 실행할 수 있는 코드로 변환하는것이다.
• 흐름도(flowchart) ≠algorithm :흐름도는 문제 해결의 절차를 그래프로 표현한것이다. 그러나 흐름도 자체는 '명백성'조건을 만족 시키지 않을 수 있다. 즉, 흐름도는 알고리즘의 개념적인 표현일뿐, 모든 세부사항이 명확하게 기술되지 않을 수 있다.

---

선택정렬 

- 정렬 알고리즘 중에 하나로 '주어진 리스트'에서 가장 작은 값을 찾아서 앞쪽부터 순서대로 정렬하는 것이다.

 

• 선택정렬의 작동방식 
  
  1. 전체 리스트에서 가장 작은 값을 찾아서 이 값을 리스트의 첫번째 위치와 교환한다.
  2. 첫번째 위치를 제외한 나머지 리스트에서 가장 작은 값을 찾는다. 이값을 리스트의 두번째 위치와 교환한다
  3. 위의 과정을 리스트의 끝까지 반복한다.
  
  
• 작동방식과 예제 
  
  주어진 리스트 'list'에 'n'개의 서로 다른정수가 있다고 가정할때, 'i'번재 정수는 'list[i]'에 저장되어 있다.
  (여기서, 1 ≤ i ≤ n)
  
  1. 'i=1'부터 시작하여 list[i]부터 list[n]까지의 원소 중 가장 작은 값을 찾는다.
  
  2. 찾은 가장 작은 값을 list[i]와 교환한다.
  
  3. i의 값을 1중가시키고,  i ≤ n인 동안 위의 과정을 반복한다.
  
  
  ex ) 주어진리스트가 list = [64, 34, 25, 12, 22, 11, 90]라고 가정할때, 
  i=0 일경우 list[i]는 64이다.
  
  첫번째 단계 (i =1)
  
  'i=1'부터 시작하여 list[i]부터 list[7]까지의 원소 중 가장 작은 값을 찾는다.
  여기서 가장작은 값은 '11'이다
  
  찾은 가장 작은 값을 list[1] (즉, 64)와 교환한다
  결과: list = [11, 34, 25, 12, 22, 64, 90]
  
  두번째단계(i =2)
  i=2로 설정하고 list[2]부터 list[7]까지의 원소중 가장작은 값을 찾는다
  찾은 가장 작은 값을 list[2](=34)와 교환한다
  
  list = [11,12,25,34,22,64,90]
  
  ....
  위 과정을 반복하여 i의 값이 n(=7)이 될때까지 반복한다. 

for (i = 0; i < n; i++) {
    list[i]에서부터 list[n-1]까지의 정수값을 검사한 결과
    list[min]이 가장 작은 정수 값이라 하자;
    list[i]와 list[min]을 서로 교환;
}

 

 

• 최소 정수를 찾는 작업
  
  - 주어진 리스트에서 현재 위치부터 끝까지의 원소 중에서 가장 작은 값을 찾는 작업을 나타낸다.
  
  1. 최소정수가정:
   현재의 i위치에 있는 정수를 일단 가장 작은값으로 가정한다. 즉 'list[i]를 현재까지의 최솟값으로 생각한다.
  
  2. 비교작업:
  list[i]의 다음 위치인 list[i+1]부터 마지막 원소 list[n-1]까지의 모든 원소와 list[i]를 비교한다
  이 비교 과정에서 list[i]보다 더 작은 값을 만나면, 그 값을 새로운 최솟값으로 선택한다
  
  3. 새로운 최솟값선택:
  비교 작업을 통해 만약 list[i] 보다 더 작은 값을 발견하면, 그값을 새로운 최솟값으로 갱신한다.
  이렇게 전체 리스트를 검사하면서 가장 작은 값을 찾게된다
  
  예)
  
  list = [50,20,40,10,30] 이라고 가정하고, i=0일때 작업을 살펴보자
  
  1. list[0](=50)을 최솟값으로 가정한다
  2. 50과 list[1]인 20을 비교한다. 20이 더 작으므로 20을 새로운 최솟값으로 선택한다
  3. 20과 list[2]인 40을 비교한다. 20이 더 작으므로, 최솟값은 변하지않는다.
  4. 20과 list[3]인 10을 비교한다. 10이 더 작으므로, 10을 새로운 최솟값을 선택한다
  
  이와 같은 과정을 반복하면 list[0]부터 list[4]까지의 원소중 가장 작은 값은 10임을 알 수 있다.
  
  
  
  

 

---

Swap 함수

 

- Swap 함수는 두개의 정수 포인터를 매개변수로 받아, 이 두 포인터가 가리키는 정수 값을 서로 교환하는 함수

 

함수정의: 

 

#include <stdio.h>

void swap(int *a, int*b){

    int temp;

    temp = *a; // 'a'가 가르키는 값을 'temp'에 저장
    *a = *b; // 'b'기 가리키는 값을 'a'가 가르키는 위치에 저장
    *b = temp; //'temp'에 저장된 값을 'b'가 가리키는 위치에 저장

}

 

사용예:

int main(){

    int x=5, y=10;
    swap(&x, &y);
    printf("x=%d, y=%d\n",x,y);
        //출력 x= 10 , yo=5
    return 0;
}

 

** 매크로란?

- #define 지시문을 사용하여 'swap'을 정의 할 수 있다.

- 매크로는 프로그래밍에서 코드나 명령의 집합을 단순화하거나 재사용하기 위한 방법 중 하나이다.

- c및 c++언어에서는 #define 지시문을 사용하여 매크로를 정의한다. 

 

1. 상수정의 : 프로그램 전체에서 변경되지 않는 값을 정의하는데 사용된다.

#define PI 3.141592653589793

 

2. 함수처럼 동작하는 메크로 : 코드조각을 단순화하거나 반복적으로 사용하는 코드를 줄이기 위해 사용된다

#define SQUARE(x) ((x) * (x))

3. Swap 함수 매크로 정의하기 

#include <stdio.h>  // 표준 입출력 함수를 위한 헤더 파일 포함

#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

int main() {
    int a = 5, b = 10, temp;
    SWAP(a, b, temp);
    printf("a=%d,b=%d\n", a, b);  // 출력: a=10, b=5
    return 0;
}