이진탐색

package study

class BinarySearchExample {
	static int binarySearch(int[] arr, int target) {
		def left = 0,
		right = arr.length - 1
		
		while (left <= right) {
			def mid = left + (right - left).intdiv(2)
			
			if(arr[mid] == target)
				return mid
			else if(arr[mid] < target)
				left = mid + 1
			else
				right = mid - 1
		}
		
		return -1
	}
	static void main(String[] args) {
		def sortedArray = [1, 3, 5, 7, 9, 11] as int[]
		def target = 7
		def result = binarySearch(sortedArray, target)
		
		println "Index of target : $result"
	}
}

- 주의사항

def mid = left + (right - left).intdiv(2) 

이 코드에서 .intdiv(2)가 아닌 / 2 를 사용했다면 Groovy에서는 BigDecimal을 반환하게 되어 배열이 정수 인덱스만 허용하기 때문에 에러가 발생하게 됨

단일 연결리스트

class Node {
    def data
    Node next

    String toString() { "$data" }
}

class LinkedList {
    Node head

    void append(data) {
        head ? head.last().next = new Node(data) : head = new Node(data)
    }

    Node last() {
        def current = head
        while (current?.next) {
            current = current.next
        }
        current
    }

    void printList() {
        def current = head
        while (current) {
            print "$current -> "
            current = current.next
        }
        println "null"
    }
}

def list = new LinkedList().with {
    append 1
    append 2
    append 3
    printList()
}

버블정렬

def bubbleSort(List<Integer> list) {
	def n = list.size()
	boolean swapped

	(0..<n-1).each{ i ->
		swapped = false
		(0..<n - i - 1).each { j ->
			if(list[j] > list[j + 1]){
				list[j..j+1] = [list[j+1], list[j]]
				swapped = true
			}
		}
		if(!swapped) return
	}
}

def arr = [5, 1, 4, 2, 8]
bubbleSort(arr)
println "Sorted: $arr"

(0..<n-1).each { i ->

• (0..<n-1)는 0부터 n-2까지의 반열림 범위(range) 생성
  ..<는 "n은 포함하지 않는다"는 의미(n-1이 마지막 숫자)
• .each{ i -> ... }는 for(int i = 0; i < n-1; i++)와 동알힌 루프

list[j..j+1] = [list[j+1], list[j]]

• list[j..j+1]은 Groovy의 슬라이싱 표현
  두 요소를 한꺼번에 바꿔끼울 수 있음
• list[j..j+1] = [list[j+1], list[j]]는 list[1]과 list[2]가 서로 바뀜

반열림 범위 vs 닫힌 범위

슬라이싱

def list = [10, 20, 30, 40, 50]

println list[1..3]    // [20, 30, 40] - 닫힌 범위
println list[1..<4]   // [20, 30, 40] - 반열린 범위 (결과 같음)
println list[-2..-1]  // [40, 50] - 음수 인덱스도 사용 가능

기타

Step() - 범위에 간격주기

(1..10).step(2).each { println it } // 1, 3, 5, 7, 9

reverse() - 범위를 역순으로

(5..1).each { println it } // 5, 4, 3, 2, 1

contains() - 특정 값이 범위에 포함되는지 확인

assert (1..5).contains(3)   // true
assert !(1..<5).contains(5) // false

선택정렬

class SelectionSortExample {
	static void selectionSort(int[] arr) {
		def n = arr.length
		
		(0..<n-1).each{ i ->
			def minIdx = i
			((i + 1)..<n).each{ j ->
				if(arr[j] < arr[minIdx]){
					minIdx = j
				}
			}
			
			def temp = arr[minIdx]
			arr[minIdx] = arr[i]
			arr[i] = temp
			
		}
	}
}
def arr = [64, 25, 12, 22, 11] as int[]
SelectionSortExample.selectionSort(arr)
arr.each{
	println it
}