Quick Sort in Swift Is Giving Error

Quick Sort in Swift is giving error

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)

Swift Quicksort Algorithm

Your computation of piv and pivot_location is wrong. It should be:

let piv = (low + (high - low) / 2)
let pivot_location = arr[piv]    

Note that I moved the division by two inside the previous calculation.

Output:

[5, 2, 4, 7, 2, 1, 3, 9, 10, 11, 7, 8]

[1, 2, 4, 7, 2, 5, 3, 9, 10, 11, 7, 8]

[1, 2, 3, 2, 7, 5, 4, 9, 10, 11, 7, 8]

[1, 2, 2, 3, 7, 5, 4, 9, 10, 11, 7, 8]

[1, 2, 2, 3, 7, 5, 4, 9, 10, 11, 7, 8]

[1, 2, 2, 3, 7, 5, 4, 8, 7, 11, 10, 9]

[1, 2, 2, 3, 4, 5, 7, 8, 7, 11, 10, 9]

[1, 2, 2, 3, 4, 5, 7, 8, 7, 11, 10, 9]

[1, 2, 2, 3, 4, 5, 7, 8, 7, 11, 10, 9]

[1, 2, 2, 3, 4, 5, 7, 7, 8, 11, 10, 9]

[1, 2, 2, 3, 4, 5, 7, 7, 8, 9, 10, 11]

[1, 2, 2, 3, 4, 5, 7, 7, 8, 9, 10, 11]

Quick Sort isn't working correctly with swapping function without temporary variable

Your "swap without temporary variable" does not work if both
arguments point to the same array element:

func swap(_ a:inout Int , _ b:inout Int) {
    a = a+b
    b = a-b
    a = a-b
}

var a = [5, 6, 7]
swap(&a[0], &a[0])
print(a) // [0, 6, 7]

Note that even passing two different elements of the same array
as inout argument to your function is undefined behavior.
In Swift 4/Xcode 9 you would get a compiler warning:

var a = [5, 6, 7]
swap(&a[0], &a[1])
// warning: overlapping accesses to 'a', but modification requires exclusive access; consider copying to a local variable

and a runtime error:

Simultaneous accesses to 0x1005e4f00, but modification requires exclusive access.

That's why the swapAt() method (taking two indices as arguments)
was added to MutableCollection in Swift 4.

See SE-0176 Enforce Exclusive Access to Memory for more information.

Bubble sorting an array in Swift, compiler error on swap

Function parameters are by default constant (as if declared with let).
If you want to modify the parameter inside your function, you have to declare it as a variable:

func sortCards(var cards: Array<Card>) -> Array<Card> { ...

Note that only the local parameter cards is modified, not the array passed as
an argument to the function (which seems to be your intention because the function
returns a new array).

Quick Sort Array Random Number Generator Nothing Printed Error

There are many problems in your code:

• You do not include <stdio.h>, <stdlib.h>, nor <time.h>.
• Your quick_sort function expects a pointer to an array of double, yet you pass an array of int.
• The code for function swap() is not posted.

• Your implementation of the Quick Sort algorithm in function quick_sort is flawed:

  • you should not scan slices of size 1, use (r - l > 1).
  • You cannot use x[l - 1] as pivot, it is not even part of the slice to be sorted. Furthermore, you should extract the pivot from the array before the swapping phase as it may move.
  • You should not name a variable l, it looks too close to 1 and you do make the mistake here: swap(&x[l1 - l], &x[r1 - 1]);
  • You should initialize l1 and r1 such that you do not need to subtract 1 in so many places, it leads to confusion and erroneous code.
  • Study the algorithms from the Wikipedia article and translate one to C.

Here is a corrected version:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 100

void swap(int *a, int *b) {
    int x = *a;
    *a = *b;
    *b = x;
}

// Quick Sort using Hoare's original partition scheme
void quick_sort(int *x, int l, int r) {
    if (l < r) {
        int pivot = x[l];
        int l1 = l - 1;
        int r1 = r;

        for (;;) {
            while (x[++l1] < pivot)
                continue;

            while (x[--r1] > pivot)
                continue;

            if (l1 < r1) {
                swap(&x[l1], &x[r1]);
            } else {
                break;
            }
        }
        quick_sort(x, l, r1 + 1);
        quick_sort(x, r1 + 1, r);
    }
}

void printArray(int a[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main(void) {
    int a[MAX];
    int a_size = sizeof(a) / sizeof(a[0]);

    srand((unsigned int)time(NULL));

    for (int i = 0; i < MAX; i++) {
        a[i] = rand() % 501;
    }
    quick_sort(a, 0, a_size);

    printArray(a, a_size);
    return 0;
}

QUICK SORT: Printing Memory Addresses instead of array elements:

In part, when l is greater than 0, starting j at 0 in part includes part of the array to the “left” of l in processing and may result in i (which was initialized to l) being incremented too many times, past r.

Changing int i=l, j=0; to int i=l, j=l; results in the program printing the desired output for the case in the question.

This problem could have been found by modifying qsort and part to print their parameters each time they are called, and to either print when they return or to indent the previous printing by the current recursion depth (which can be tracked, for debugging purposes, with a static counter). This promptly reveals a call to qsort with r set to 9, beyond the array, which then leads to examining how it came to be that way.

Incorrect Array Sorting when using Swift sorted(by:) method

This happens because the strings are sorted as strings, i.e. lexicographically. Therefore, "1" precedes both "6" and "7", so the list is sorted correctly.

A quick fix to this problem is to add zeros to four-character strings representing time, i.e. change your list to

["07:56", "14:57", "11:57", "06:58", "10:59", "17:59"]

This list would sort correctly. If this is not an option, use a custom comparer, as described in this Q&A.

Sorting large arrays (QuickSort) - segmentation fault

I see two errors here, first one:
You don't check the value of argc before using argv. If you give no arguments to your program, you'll end up sending undefined addresses to atoi here:

a_size = atoi(argv[1]);
t_num = atoi(argv[2]);

Second one:

    a_size = atoi(argv[1]);

atoi() returns an int which can't be superior to 2147483647 (2^31), otherwise it overflows and end up being lower than 0.

Does this sorting algorithm exist? (implemented in Swift)

This is an extreme version of radix sort. Quoted from Wikipedia:

radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort.

In this case you choose your radix as maxSpace, and so you don't have any "elements with more than one significant digit" (from quote above).

Now, if you would use a Hash Set data structure instead of an array, you would actually not need to really allocate the space for the whole range. You would still keep all the loop iterations though (from 0 to maxSpace), and it would check whether the hash set contains the value of i (the loop variable), and if so, output it.

This can only be an efficient algorithm if maxSpace has the same order of magnitude as the number of elements in your input array. Other sorting algorithms can sort with O(nlogn) time complexity, so for cases where maxSpace is much greater than nlogn, the algorithm is not that compelling.

---

Related Topics