exp_blog

버블 정렬(bubble sort) 알고리즘 개념 

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
  • 인접한 2개의 레코드 비교, 크기가 순서대로 되어있지 않으면 서로 교환
• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, …
  이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬
• 1회전 수행하면 가장 큰 자료가 맨 뒤로 이동 하므로 2회전에는 맨 끝에 있는 자료는 제외되고, 
  2회전에는 끝에서 두 번째 자료까지는 정렬에서 제외 
  => 정렬을 1회전 수행할때마다 정렬에서 제외되는 데이터가 하나씩 증가 

알고리즘 특징

• 장점
  • 구현이 매우 간단하다.(옆에 레코드와 비교해서 큰 값을 뒤로 넘겨주면 됨)
• 단점
  • 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
  • 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
  • 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

시간 복잡도

• 비교 횟수
  최상, 평균, 최악 모두 일정
  n-1, n-2, … , 2, 1 번 = n(n-1)/2
• 교환 횟수
  • 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
  • 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
• T(n) = O(n^2)

버블 정렬(bubble sort)의 c언어 코드 

# include <stdio.h>
# define MAX_SIZE 5

// 버블 정렬
void bubble_sort(int list[], int n){
  int i, j, temp;

  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;
      }
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {7, 4, 5, 1, 3};

  // 버블 정렬 수행
  bubble_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

Go언어로 된 버블 정렬 알고리즘은?

//bubble sort func
package bubblesort

func Bubble_sort(array []int) []int {
	for i := 0; i < len(array)-1; i++ {
		for j := 0; j < len(array)-i-1; j++ {
			if array[j] > array[j+1] {
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
	return array
}


//main
package main

import (
	"fmt"
	"study01/package1/bubblesort"
)
func main() {
	fmt.Print(bubblesort.Bubble_sort([]int{11, 8, 2, 3, 4, 5}))
}

개요

고에서는 array, slice, map을 지원한다

slice는 가변적인 배열로 , 파이썬에서는 list

map은 key-vaule 의 형태의 자료형으로 dict로 생각하면 된다. 

slice와 map은 함께 많이 사용한다. 어떻게 사용하는지 정리해본다. 

배열

package array

import "fmt"

func NewArray(){
	var a [5]int // 다른 데이터 형태와는 달리 var 변수명 뒤에 자료형을 생략할 수 없음
	b := [4]int{1,2,3,4} //배열은 선언과 동시에 초기화가 가능

	fmt.Println(a,len(a))
	fmt.Println(b, len(b))
}

[0 0 0 0 0] 5 // 값을 지정하지 않으면 0 으로 초기화
[1 2 3 4] 4

슬라이스

package slice


func NewSlice(){
	// slice 선언 두가지 방법으로
    var a []int
    b := make([]int,5,10)
    //int 자료형인 길이 5, 최대 길이 10 
     
    //즉, slice는 고정길이 배열과 달리 초기화시 최대 길이를 지정할 수 있고,
    //해당 slice를 통해 최대 길이를 넘지 않는 범위에서 가변길이 배열(=슬라이스)을 얼마든 생성해낼 수 있다

	//append같은 메소드를 사용하면 슬라이스의 길이를 확장시킬 수 있다
    b = append(a, 5,2,3,4)
    fmt.Println(a,b)
}

[] [5 2 3 4]

슬라이스와 배열의 차이는 가변 길이를 정하는 것이고, 

리스트 선언 시 길이를 명시해주면 배열(생성한 길이 만큼만 사용할 수 있음)

길이를 명시하지 않으면 슬라이스(유연하게 조정하고 늘려가며 사용할 수 있음)

맵

package map1

import "fmt"


func NewMap(){
	// 주어진 타입을 초기화하고 사용할 수 있는 맵을 반환
	
	a := make(map[int]string)
	a[1] = "A"
	a[2] = "B"

	// 초기화 시 값을 넣어서 맵을 반환할 수 있음 
	map_int_str := map[int]string {
		1: "월",
		2: "화",
		3: "수",
		4: "목",
		5: "금",
		6: "토",
		7: "일",
		//마지막 값 입력 시에도 , 가 빠지면 에러
		}

	fmt.Println(a,map_int_str)
	//map[1:A 2:B] map[1:월 2:화 3:수 4:목 5:금 6:토 7:일]
}

만약 없는 요소라면? 숫자일 경우에는 0을 문자열의 경우에는 "" 을 출력한다 

 // 만약, 값이 주어지지 않은 요소를 꺼내온다면?

package map1

import "fmt"

func NotInMap(){
	a := make(map[int]int)

	a[1] = 2
	a[3] = 4

	fmt.Println(a[2])
}
// 0

정확히 맵은 어떤 타입을 반환하는걸까 보면 

package map1

import "fmt"

func NotInMap(){
	a := make(map[int]int)

	a[1] = 2
	a[3] = 4

	value1, ok := a[1]
	fmt.Println(value1,ok)
	// 2 true

	value2, ok := a[2]
	fmt.Println(value2,ok)
	// 0 false 

	value3,ok := a[3]
	fmt.Println(value3,ok)
	// 4 true
}

존재하지 않는 키 값을 요청한다면, 두 번째 인자로 false 를 반환한다. 

아래는 맵의 요소 확인과 삭제 문법

package map1

import "fmt"

func NotInMap(){
	a := make(map[int]int)

	// 맵에 요소를 추가하거나 업데이트 
	a[1] = 2
	a[3] = 4

	value1, ok := a[1]
	fmt.Println(value1,ok)
	// 2 true

	value2, ok := a[2]
	fmt.Println(value2,ok)
	// 0 false 

	// 요소 제거 
	delete(a,3)

	value3,ok := a[3]
	fmt.Println(value3,ok)
	// 0 false
}

따라서 go에서는 아래와 같이 예외 처리를 한다. 

package map1

import "fmt"

func NotInMap(){
	a := map[int]int{
		1 : 2,
		2 : 3,
		3 : 4,
		4 : 5,
	}
	
	// key를 0~7까지 대입하고, a[key] 의 결과로 ok 값을 받아 
	//ok가 true일 경우(해당 키에 대한 value값 존재 시 ) key에 해당하는 value를 출력
	//그렇지 않을 경우(false/ value값이 미존재 시 ) 문자열 출력
	for key:= 0; key < 8; key++{
		if value, ok := a[key];ok{
				fmt.Println(value)
			} else {
			fmt.Println("key", key, "is not exist")
		}
	}
}

key 0 is not exist
2
3
4
5
key 5 is not exist
key 6 is not exist
key 7 is not exist

go tour > 맵 연습하기 (링크 : https://go-tour-ko.appspot.com/moretypes/23) 

// go tour map 연습하기

// 문자열 s가 주어진다
//주어진 문자열을 단어 단위로 나눠 단어가 몇번 쓰였는지 맵으로 기록한다
// wc.test 함수로 우리가 작성한 함수를 여러 테스트 케이스로 테스트해준다.

package map1

import (
	"strings"

	"golang.org/x/tour/wc"
)

func WordCount(s string) map[string]int {
	//strings filed는 유니코드에서 정의한 대로 
	//하나 이상의 연속된 공백 문자의 각 인스턴스를 기준으로 문자열 분할
	words := strings.Fields(s)
	//일단 문자열을 단어 단위의 배열로 반환 

	result := make(map[string]int)

	// for 인덱스 , 요소 := range 배열 {...}
	// 아래는 요소만 사용할 때 
	for _, w:= range words{
		if result[w] == 0 {
			result[w] = 1
		}else{
			result[w] = result[w] +1
		}
	}
	return result
}


func main() {
	wc.Test(WordCount)
}

//PASS
 f("I am learning Go!") = 
 map[string]int{"Go!":1, "I":1, "am":1, "learning":1}
PASS
f("The quick brown fox jumped over the lazy dog.") = 
 map[string]int{"The":1, "brown":1, "dog.":1, "fox":1, "jumped":1, "lazy":1, "over":1, "quick":1, "the":1}
PASS
f("I ate a donut. Then I ate another donut.") = 
 map[string]int{"I":2, "Then":1, "a":1, "another":1, "ate":2, "donut.":2}
PASS
f("A man a plan a canal panama.") = 
 map[string]int{"A":1, "a":2, "canal":1, "man":1, "panama.":1, "plan":1}