• C언어 문법은 일단 여기까지
  
• 본격적 알고리즘 시작
  
• 선형 자료 구조(linear data structure)
  
  • 배열(array) : fixed-sized collection of contiguous data
    
    • random access
      
  • 연결 리스트(linked list) : sequential of data linked by pointer
    
    • node - link
      
  • array v.s. linked list
    
• algorithms for sequential data
  
  • 탐색(search)
    
    • 선형 탐색(linear search)
      
    • 이진 탐색(binary search)
      
  • 정렬(sort)
    
    • 선택 정렬(selection sort)
      
    • 삽입 정렬(insertion sort)
      
    • 병합 정렬(merge sort)
      
      • divide-and-conqurer
        
    • 퀵 정렬(quick sort)
      
    • performance
      
      • big-O notation(big-Omega, big-Theta)
        
      • speed, time complexity
        
      • memory, space complexity, in-place sort
        
      • stablity
        
    • swap sort v.s. others
      
      • e.g) counting sort, radix sort
        
  • 이번주는 일정이 안맞아 휴강; 다음주에 이 내용으로 진행합니다.
    

• selection_sort, insertion_sort, merge_sort, quick_sort(,bubble_sort : optional)
  
• <sort_instruction> input_file [output_file]
  
• any language
  
• input :
  
  • 1st line : # of line N
    
  • 2nd ~ : (unsorted) N integers
    
• output:
  
  • N line : sorted N integers
    
  • N + 1 line : elapsed time (in millisecond)
    
  • print in output file; if no argument, to standard output(terminal console)
    
    

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

#define swap(type,x,y) type t = x; x = y; y = t; //교환함수

void selection(void); //선택정렬
void insertion(void); //삽입정렬
void merge(int,int); //병합정렬
void quick(int,int); //퀵정렬
void bubble(void); //버블정렬
void output(char*); //(output.txt로 정렬된 수열과 elapsed time 출력) or 표준출력

int n;
int *a;
int *buff;

double milsec;
time_t start, end;

FILE *input_file;
FILE *output_file;

int main(int argc, char* argv[]){
  int i;
  char num[10]; //n은 1,000,000,000미만.

  input_file = fopen(argv[2],"r");
  output_file = fopen(argv[3],"w");

  if(input_file == NULL){;
    printf("ERROR_InputFile\n");
    return 0;
  }//input_file이 존재하지 않으면 에러 출력.

  fgets(num,sizeof(num),input_file);
  n = atoi(num); //배열의 크기 N을 구함.
  a = calloc(n,sizeof(int));

  for(i=0;i<n;i++){
    fscanf(input_file,"%d",&a[i]); //배열 a에 정렬되지 않은 수 받기.
  }

  //명령받기.
  if(!strcmp(argv[1],"selection")) selection();
  else if(!strcmp(argv[1],"insertion")) insertion();
  else if(!strcmp(argv[1],"merge")){
    buff = calloc(n,sizeof(int));
    merge(0,n-1);
    free(buff);
  }
  else if(!strcmp(argv[1],"quick")) quick(0,n-1);
  else if(!strcmp(argv[1],"bubble")) bubble();
  else printf("Wrong_SortInstruction");

  //결과출력.
  output(argv[3]);

  //배열해제 및 파일닫기.
  free(a);
  fclose(input_file);
  fclose(output_file);

  return 0;
}

//선택정렬
void selection(void){
  start = clock();
  int i, j;
  for(i=0;i<n-1;i++){
    int min = i;
    for(j=i+1;j<n;j++){
      if(a[j]<a[min]){
        min = j;
      }
    }
    swap(int,a[i],a[min]);
  }
  end = clock();
}

//삽입정렬
void insertion(void){
  start = clock();
  int i,j;
  for(i=1;i<n;i++){
    int tmp = a[i];
    for(j=i; j>0 && a[j-1]>tmp; j--){
      a[j] = a[j-1];
    }
    a[j] = tmp;
  }
  end = clock();
}

//병합정렬
void merge(int left, int right){
  start = clock();
  if(left<right){
    int i, j = 0, k = left, p = 0;
    int center = (left + right) / 2;
    merge(left,center);
    merge(center+1,right);
    for(i=left;i<=center;i++){
      buff[p++] = a[i];
    }
    while(i<=right && j<p){
      a[k++] = (buff[j]<=a[i]) ? buff[j++] : a[i++];
    }
    while(j<p){
      a[k++] = buff[j++];
    }
  }
  end = clock();
}

//퀵정렬
void quick(int left, int right){ //재귀적인 방식.
  start = clock();
  int pl = left;
  int pr = right;
  int x = a[(pl+pr)/2];
  do{
    while(a[pl] < x) pl++;
    while(a[pr] > x) pr--;
    if(pl <= pr){
      swap(int,a[pl],a[pr]);
      pl++;
      pr--;
    }
  }while(pl <= pr);
  if(left < pr) quick(left,pr);
  if(pl < right) quick(pl,right);
  end = clock();
}//비재귀적인 방법은 스택을 활용.

//버블정렬
void bubble(void){
  start = clock();
  int i = 0, j;
  while(i<n-1){
    int last = n-1; //가장 마지막으로 교환이 일어난 위치
    for(j=n-1;j>i;j--){
      if(a[j]<a[j-1]){
        swap(int,a[j],a[j-1]);
        last = j;
      }
    }
    i = last;
  }
  end = clock();
}

//출력함수
void output(char* argv){
  int i;
  milsec = 1000.0 * (end-start) / CLOCKS_PER_SEC;
  if(argv){
    for(i=0;i<n;i++){
      fprintf(output_file,"%d ",a[i]); //정렬된 배열 a 출력
    }
    fprintf(output_file,"\n");
    fprintf(output_file,"elapsed_time = %.3f ms\n",milsec); //elapsed_time 출력
  }
  else{
    for(i=0;i<n;i++){
      printf("%d ",a[i]);
    }
    printf("\n");
    printf("elapsed_time = %.3f ms\n",milsec);
  }
}
//힘들어ㅠㅠ

def swap(x, i, j) :
    x[i], x[j] = x[j], x[i]
    
def s_selection(x) :
    for s in reversed(range(len(x))) :
        max_i = 0;
        for i in range(1, 1+s) :
            if x[i] > x[max_i] :
                max_i = i
        swap(x, max_i, s)
        
def s_insertion(x) :
    for s in range(1, len(x)) :
        tmp = x[s]
        i = s
        while i > 0 and x[i-1] > tmp :
            x[i] = x[i-1]
            i -= 1
        x[i] = tmp
        
def s_merge(x) :
    if len(x) > 1 :
        mid = len(x)//2
        l_x, r_x = x[:mid], x[mid:]
        s_merge(l_x)
        s_merge(r_x)
        
        l_i, r_i, i = 0, 0, 0
        while l_i < len(l_x) and r_i < len(r_x) :
            if l_x[l_i] < r_x[r_i] :
                x[i] = l_x[l_i]
                l_i += 1
            else :
                x[i] = r_x[r_i]
                r_i += 1
            i += 1
        x[i:] = l_x[l_i:] if l_i != len(l_x) else r_x[r_i:]
        
def pivotFirst(x, lmark, rmark):
    pivot_val = x[lmark]
    pivot_idx = lmark
    while lmark <= rmark:
        while lmark <= rmark and x[lmark] <= pivot_val:
            lmark += 1
        while lmark <= rmark and x[rmark] >= pivot_val:
            rmark -= 1
        if lmark <= rmark:
            swap(x, lmark, rmark)
            lmark += 1
            rmark -= 1
    swap(x, pivot_idx, rmark)
    return rmark
def s_quick(x, pivotMethod=pivotFirst):
    def _qsort(x, first, last):
        if first < last:
            splitpoint = pivotMethod(x, first, last)
            _qsort(x, first, splitpoint-1)
            _qsort(x, splitpoint+1, last)
    _qsort(x, 0, len(x)-1)
    
def s_bubble(x) :
    for s in reversed(range(len(x))):
        for i in range(s):
            if x[i] > x[i+1]:
                swap(x, i, i+1)
                
             
import sys
import timeit

if __name__ == "__main__" :   
    try :
        input_file = open(sys.argv[2], 'r')
    except FileNotFoundError as e :
        print(str(e))
        exit(0)
    
    n = input_file.readline()
    data = str(input_file.read()).split()
    data = [int(i) for i in data]
            
    option = sys.argv[1]
    t_start = timeit.default_timer()
    if 's' in option :
        s_selection(data)
    elif 'i' in option :
        s_insertion(data)
    elif 'm' in option :
        s_merge(data)
    elif 'q' in option :
        s_quick(data)
    elif 'b' in option :
        s_bubble(data)
    else :
        s_bubble(data)
    t_end = timeit.default_timer()
        
    try :
        tmp = sys.argv[3]
        output_file = open(tmp, 'w')
    except :
        output_file = open("o_"+sys.argv[2], 'w')
            
    for d in data :
        output_file.write(str(d) + ' ')
    output_file.write("\n");
    output_file.write("%s" % (t_end - t_start))
    
    input_file.close()
    output_file.close()