data_structure_go/sorting_algorithm.go at master · CORE-BAN/data_structure_go · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package data_structure_go

import "fmt"

type sortingAlgorithm struct {
	Array *[]int
}

func NewSortingAlgorithm(array *[]int) *sortingAlgorithm {
	return &sortingAlgorithm{
		Array: array,
	}
}

func (s *sortingAlgorithm) BubbleSortDescending() {
	for i := 0; i < len(*s.Array); i++ {
		for j := 0; j < len(*s.Array)-1; j++ {
			if (*s.Array)[j] < (*s.Array)[j+1] {
				temp := (*s.Array)[j]
				(*s.Array)[j] = (*s.Array)[j+1]
				(*s.Array)[j+1] = temp
			}
		}
	}
}

func (s *sortingAlgorithm) BubbleSortAscending() {
	for i := 0; i < len(*s.Array); i++ {
		for j := 0; j < len(*s.Array)-1; j++ {
			if (*s.Array)[j] > (*s.Array)[j+1] {
				temp := (*s.Array)[j]
				(*s.Array)[j] = (*s.Array)[j+1]
				(*s.Array)[j+1] = temp
			}
		}
	}

}

func (s *sortingAlgorithm) PrintArray() {
	for _, data := range *s.Array {
		fmt.Print(data, ", ")
	}
	fmt.Println("")
}

func (s *sortingAlgorithm) QuickSortAscending() {
	s.quickSortRecursiveAscending(len(*s.Array)-1, 0)
}

func (s *sortingAlgorithm) quickSortRecursiveAscending(high, low int) {
	if low < high {
		pivot := s.partitionAscending(high, low)
		s.quickSortRecursiveAscending(pivot-1, low)
		s.quickSortRecursiveAscending(high, pivot+1)
	}
}

func (s *sortingAlgorithm) partitionAscending(high, low int) int {
	pivot := (*s.Array)[high]
	i := low - 1
	for j := low; j < high; j++ {
		if (*s.Array)[j] <= pivot {
			i++
			temp := (*s.Array)[i]
			(*s.Array)[i] = (*s.Array)[j]
			(*s.Array)[j] = temp
		}

	}
	temp := (*s.Array)[i+1]
	(*s.Array)[i+1] = (*s.Array)[high]
	(*s.Array)[high] = temp
	return i + 1
}

func (s *sortingAlgorithm) QuickSortDescending() {
	s.quickSortRecursiveDescending(len(*s.Array)-1, 0)

}

func (s *sortingAlgorithm) quickSortRecursiveDescending(high, low int) {
	if low < high {
		pivot := s.partitionDescending(high, low)
		s.quickSortRecursiveDescending(pivot-1, low)
		s.quickSortRecursiveDescending(high, pivot+1)
	}
}

func (s *sortingAlgorithm) partitionDescending(high, low int) int {
	pivot := (*s.Array)[high]
	i := low - 1
	for j := low; j < high; j++ {
		if (*s.Array)[j] >= pivot {
			i++
			temp := (*s.Array)[i]
			(*s.Array)[i] = (*s.Array)[j]
			(*s.Array)[j] = temp
		}

	}
	temp := (*s.Array)[i+1]
	(*s.Array)[i+1] = (*s.Array)[high]
	(*s.Array)[high] = temp
	return i + 1
}