Sorting algorithm help, what Divide and Conquer algorithm is this?

user_19352985 0
Viewed 40

first time poster here.

I was practicing some sorting algorithms in Go-lang. I tried to write a quick sort algorithm. The code can be seen below.

func DivideAndConquerSort(newArr []int,descending bool) []int {

    if len(newArr) == 1 || len(newArr) == 0{
        return newArr
    }
    pivotIndex := 0
    leftPivot := []int{}
    rightPivot := []int{}
    centerPivot := []int{}
    for idx1 := 0; idx1<len(newArr); idx1++{
        if newArr[pivotIndex] == newArr[idx1]{
            centerPivot = append(centerPivot,newArr[idx1])
            continue
        }
        
        if descending {
            if newArr[pivotIndex] < newArr[idx1]{
                leftPivot = append(leftPivot,newArr[idx1])
                continue
            }
            if newArr[pivotIndex] > newArr[idx1]{
                rightPivot = append(rightPivot,newArr[idx1])
                continue
            }
        }
        if newArr[pivotIndex] > newArr[idx1]{
            leftPivot = append(leftPivot,newArr[idx1])
            continue
        }
        if newArr[pivotIndex] < newArr[idx1]{
            rightPivot = append(rightPivot,newArr[idx1])
            continue
        }
    }
    leftPivot = DivideAndConquerSort(leftPivot,descending)
    leftPivot = append(leftPivot,centerPivot...)
    
    rightPivot = DivideAndConquerSort(rightPivot,descending)
    
    newArr = append(leftPivot,rightPivot...)
    
    return newArr
}

But the more I look at it. It more looks like a Merge Sort..?. I'm not really sure at this point.

I'm referencing the definition and flow of the algorithms from pediaa.com.

Essentially I thought this is a Quick Sort because I'm using pivot and comparing them. But strangely I don't think the code did any swaps ( which quick sort should do ). With that in mind, I'm inclined to say that it was a Merge Sort. But again, I'm not sure, the website doesn't state that Merge uses pivots.

Can you guys enlighten me of what kind of sorting algorithm I wrote?. Also, I'm open towards criticism towards how I write my code.

go sorting algorithm
1 Answers

This algorithm is essentially a version of quicksort. It picks a pivot, partitions the input array into three groups of items (items smaller than, equal to, and greater than the pivot), then recursively sorts the items that are smaller than and bigger than the pivot.

You’re correct that the algorithm isn’t making any swaps. Unlike a traditional quicksort, which modifies the array in-place, this algorithm creates new arrays to hold the elements that are smaller than, equal to, and bigger than the pivot. That makes it less efficient than a standard quicksort implementation. But in spirit this is indeed a quicksort.

user_5015570
Related