CODEWITHSUNDEEP
swiftswift3
Rahul
Rahul

Reputation: 2100

Quick Sort in Swift is giving error

I am writing a Quick Sort using higher order function in Swift but it is giving 

error: 'Int' is not convertible to '[Int]'
return quickSort(array: lesser) + [pivot] + quickSort(array: greater)

Here is the code:

func quickSort(array: [Int]) -> [Int] {
    var array = array

    if array.isEmpty {return []}

    let pivot = array.remove(at: 0)
    let lesser = array.filter { $0 < pivot }
    let greater = array.filter { $0 >= pivot }

    return quickSort(array: lesser) + [pivot] + quickSort(array: greater)

}

Error is in the last line.

Upvotes: 3

Views: 227

Answers (3)

Anand Nigam
Anand Nigam

Reputation: 138

You can try this too

func partition(_ inputArray: [Int], startIndex: Int, endIndex: Int)-> (Int, [Int]) {
    var array = inputArray
    var index = startIndex
    if startIndex < endIndex {
        let pivot = array[endIndex]

        for demo in startIndex..<endIndex {
            if array[demo] <= pivot {
                (array[index], array[demo]) = (array[demo], array[index])
                index += 1
            }
        }
        (array[index], array[endIndex]) = (array[endIndex], array[index])

    }
   return (index, array)
}


func QuickSort(_ input: [Int], startIndex: Int, endIndex: Int)-> [Int] {
    var array = input
    if startIndex < endIndex {
         let pivot = partition(array, startIndex: startIndex, endIndex: endIndex)
       let index = pivot.0
        array = pivot.1
       array = QuickSort(array, startIndex: startIndex, endIndex: index-1)
        array = QuickSort(array, startIndex: index+1, endIndex: endIndex)
    }
    return array
}

Upvotes: 0

Alain T.
Alain T.

Reputation: 42133

It is indeed the compiler getting confused with data types in a multi operation formula involving the return type of the function it is currently compiling.

There are probably a multitude of ways to help the compiler along . Here's one that doesn't involve redundant type casting (the key is making pivot an [Int] array):

func quickSort(array: [Int]) -> [Int] 
{
    if array.count < 2 { return array }

    let pivotValue = array.first!  
    let lesser     = array.filter{ $0 < pivotValue }
    let greater    = array.filter{ $0 > pivotValue }
    let pivot      = Array(repeating: pivotValue, 
                               count: array.count - lesser.count - greater.count) 

    return  quickSort(array:lesser) + pivot + quickSort(array:greater)
}

Upvotes: 0

Luca Angeletti
Luca Angeletti

Reputation: 59536

I can't tell you why it does not work (I think it should), but I can tell you how to fix it

Replace this

return quickSort(array: lesser) + [pivot] + quickSort(array: greater)

with this

return
    quickSort(array: lesser) as [Int] +
    [pivot] +
    quickSort(array: greater)

Upvotes: 3

Related Questions