Hi, I’m trying to make a QuickSort algorithm but for some reason it only works with some arrays.
For example with
{6, 9, 3, 4, 6, 5}
it works perfectly:
but when I try a different table, like:
{505, 202, 603, 0, 1, 6}
it fails, as you can see here:
505 is in the middle which just doesn’t make sense at all.
Here is my code:
local initialArray = {505, 202, 603, 0, 1, 6}
local function swap(array, i1, i2)
local first = array[i1]
local second = array[i2]
array[i1] = second
array[i2] = first
end
local function quickSort(array)
local pivotIndex = 1
local compareTo = #array
for at,v in ipairs(array) do
if at > 1 and v < compareTo then
swap(array, pivotIndex, at)
pivotIndex += 1
end
end
swap(array, pivotIndex, compareTo)
return array
end
print(quickSort(initialArray))
I’m not sure what I’m doing wrong as I haven’t understood this algorithm completely, I was following an explanation.
Thank you!
This isn’t QuickSort, this is closer to BubbleSort. If you want to create a QuickSort algorithm, then you need to follow these steps.
If the length of the table is 1, return. If it’s 2, or 3, then sort it manually and return.
Select a pivot point. There are many ways to go about this, such as taking a random value from the array or taking multiple values from the array and finding median of them.
Sort the table such that values less than the pivot come before it, while values greater than the pivot come after it. In some implementations, the values are not rearranged in the array, but instead get put in separate tables.
QuickSort the values that are less than the pivot, then QuickSort the values greater than the pivot.
Thank you, I tried to follow your explanation but sadly it doesn’t work.
local function quickSort(array)
local length = #array
if length == 1 then
return array[1]
elseif length == 2 then
return array[1] > array[2] and {array[1], array[2]} or {array[2], array[1]}
elseif length == 3 then
local greatest = math.max(array[1], array[2], array[3])
local lowest = math.min(array[1], array[2], array[3])
local middle
for _,v in ipairs(array) do
if v ~= lowest and v ~= greatest then
middle = v
end
end
return {lowest, middle, greatest}
else
local pivotPoint = array[length]
local smaller = {}
local greater = {}
for _,v in ipairs(array) do
if pivotPoint > v then
table.insert(smaller, v)
else
table.insert(greater, v)
end
end
quickSort(smaller)
quickSort(greater)
--combine the tables
local combined = {}
for _,v in ipairs(smaller) do
table.insert(combined, v)
end
for _,v in ipairs(greater) do
table.insert(combined, v)
end
return combined
end
end
local t = {5, 1, 5, 2, 7, 8, 2, 1}
local quickSorted = quickSort(t)
print(quickSorted)
The issue with your code was that it was getting stuck on specific groupings of numbers because you were including the pivot in the quick sort.
-- Includes the pivot in the next sort
-- Will cause the algorithm to halt at specific conditions
for _,v in ipairs(array) do
if pivotPoint > v then
table.insert(smaller, v)
else
table.insert(greater, v)
end
end
-- Only includes values from index 1, to #array - 1 in the next sort
for i = 1, length - 1 do
if pivotPoint >= v then
table.insert(smaller, v)
else
table.insert(greater, v)
end
end
-- After sorting smaller and larger, merge smaller
-- followed by pivot followed by larger into one table
for _,v in ipairs(smaller) do
table.insert(combined, v)
end
table.insert(combined, pivotPoint)
for _,v in ipairs(greater) do
table.insert(combined, v)
end
Unfortunately, it’s still not working.
Here, my script:
local function quickSort(array)
local length = #array
if length == 1 then
return array[1]
elseif length == 2 then
return array[1] > array[2] and {array[1], array[2]} or {array[2], array[1]}
elseif length == 3 then
local greatest = math.max(array[1], array[2], array[3])
local lowest = math.min(array[1], array[2], array[3])
local middle
for _,v in ipairs(array) do
if v ~= lowest and v ~= greatest then
middle = v
end
end
return {lowest, middle, greatest}
else
local pivotPoint = array[length]
local smaller = {}
local greater = {}
for i = 1, length - 1 do
local v = array[i]
if pivotPoint >= v then
table.insert(smaller, v)
else
table.insert(greater, v)
end
end
quickSort(smaller)
quickSort(greater)
--combine the tables
local combined = {}
for _,v in ipairs(smaller) do
table.insert(combined, v)
end
table.insert(combined, pivotPoint)
for _,v in ipairs(greater) do
table.insert(combined, v)
end
return combined
end
end
local t = {5, 1, 5, 2, 7, 8, 2, 1}
local quickSorted = quickSort(t)
print(quickSorted)
First, the error for things timing out is because not all trivial cases are handled. If you sort the array: {10,9,5,8,7,1}, then you’re going to split it into {}, 1, {10,9,5,8,7}
This will cause the else statement to run and recursively call itself passing in empty tables for ‘smaller’ and ‘greater’.
Then, you’ll want to set the return values of you’re quickSort calls:
So instead of returning a table that includes both, smaller and greater (and the pivotpoint in the middle), I should just return smaller and greater?
Like this?
local function quickSort(array)
local length = #array
if length == 1 then
return array[1]
elseif length == 2 then
if array[1] > array[2] then
return {array[1]}, {array[2]}
else
return {array[2]}, {array[1]}
end
elseif length == 3 then
local greatest = math.max(array[1], array[2], array[3])
local lowest = math.min(array[1], array[2], array[3])
local middle
for _,v in ipairs(array) do
if v ~= lowest and v ~= greatest then
middle = v
end
end
return {lowest, middle}, {greatest}
else
local pivotPoint = array[length]
local smaller = {}
local greater = {}
for i = 1, length - 1 do
local v = array[i]
if pivotPoint >= v then
table.insert(smaller, v)
else
table.insert(greater, v)
end
end
smaller = quickSort(smaller)
greater = quickSort(greater)
return smaller, greater
end
end
local t = {5, 1, 5, 2, 7, 8, 2, 1}
local smaller, greater = quickSort(t)
print(smaller, greater)
Hmm, idk u might have went a little off track. No worries tho,
First, you still want the algorithm to always return a single table. Sorry to have confused you on that - but you still want to merge everything that was initially in the array after sorting the parts.
Here’s a version I wrote up and some additional points on it
local function quickySort(arr)
local n = #arr
if n<=1 then
return arr -- Already sorted if 1 or less elements
elseif n==2 then -- Easy to sort two elements
return arr[1]<arr[2] and arr or {arr[2], arr[1]}
else -- Array is big (split into smaller arrays, sort those, then put back together)
local pivotVal = arr[1] -- Choose pivot
local smaller, greater = {}, {}
for i=2, n do
table.insert(arr[i]<=pivotVal and smaller or greater, arr[i])
end -- Split into two tables
smaller = quickySort(smaller) -- Sort everything below pivot
greater = quickySort(greater) -- Sort everything above pivot
local merged = {} -- Merge both tables and pivot together in sorted order
for _, v in ipairs(smaller) do table.insert(merged, v) end
table.insert(merged, pivotVal)
for _, v in ipairs(greater) do table.insert(merged, v) end
return merged
end
end
The algorithm might choose a terrible pivot, where every other number is higher than it. So you’ll need to handle arrays which have 0 elements. The first if statement above does that.
The second if statement just sorts a table of two items, which actually isn’t needed. This can work with just the first and last if statements.
I agree!
But I think having it on one line, makes the functionality appear more atomic which makes sense with other languages. Like how python arrays use the ‘+’ operator to concat arrays.
Since the sole purpose of this loop is to perform the same atomic operation on an entire table - why not express that in the same line declaring the iteration rules.
In english I would read them as:
for _, v in ipairs(tab1) do table.insert(tab2, v) end
For every value in this table insert it into this other table.
And
for _, v in ipairs(tab1) do
table.insert(tab2, v)
end
For every value in this table,
– insert it into this other table
I don’t think either is better or more correct, as @itsLevande said personal preference. But kinda cool to think about why I did that the way I did that.
in my opinion it really depends on what you like more, I personally think that beginners would be able to understand it better(in three lines), but that obviously won’t go for everyone
an example is how some people in js leave one line for a “{” and some don’t, it’s just what you like more
