A Sorting Algorithm

Question

I've written this sorting algorithm in C. It looks for the element with the max value every iteration and adds it to the end of the array, swapping it with other smaller elements. This way, by almost n swaps, an n element array can be sorted.

#include <stdio.h> int max(int arr1[],int l){ int max = 0; for(int i = 0; i <= l;i++) max = (arr1[i] > arr1[max]) ? (i) : (max); return max; } void swap(int arr[], int a,int b){ if(arr[a] != arr[b]){ arr[a] += arr[b]; arr[b] = arr[a] - arr[b]; arr[a] -= arr[b]; } } int main(){ int arr[] = {1,5,7,2,8,9,10,32,4}; int len = sizeof(arr) / sizeof(arr[0]); for(int i = 0; i < len; i++) swap(arr,(len - i - 1),max(arr,(len - i -1))); printf("\nSorted Array:\n"); for(int i = 0; i < len;i++) printf("%d ",arr[i]); } 

Any suggestions/constructive criticism are very welcome. I'm a beginner, please point out any mistakes I made.

Answer 1

The Swap

It's the good old "arithmetic swap", a variant of the XOR-swap that uses addition and subtraction instead of XOR. It avoids naming a temporary variable, which was not a significant cost, and instead introduces a handful of extra operations.. and the potential for integer overflow (admittedly it is likely to work in practice, and will work for this example thanks to the small numbers).

Here's the assembly for that kind of swap vs a "traditional swap", as compiled by Clang:

swap: # @swap movsxd rax, esi mov esi, dword ptr [rdi + 4*rax] movsxd rcx, edx mov edx, dword ptr [rdi + 4*rcx] cmp esi, edx je .LBB0_2 add edx, esi mov dword ptr [rdi + 4*rax], edx sub edx, dword ptr [rdi + 4*rcx] mov dword ptr [rdi + 4*rcx], edx sub dword ptr [rdi + 4*rax], edx .LBB0_2: ret swap_tmp: # @swap2 movsxd rax, esi mov ecx, dword ptr [rdi + 4*rax] movsxd rdx, edx mov esi, dword ptr [rdi + 4*rdx] mov dword ptr [rdi + 4*rax], esi mov dword ptr [rdi + 4*rdx], ecx ret 

I don't recommend the XOR-swap except in special cases (it does work well to swap bits within an integer), I don't recommend the arithmetic-swap basically at all.

Passing the highest valid index vs the length

The parameter l passed to max is not a length (which its name sort of suggests it is), it's the highest valid index. That's possible of course, but not idiomatic, and leads to a random-looking "subtract 1", and an out-of-place-looking <= in the condition of a for-loop. That works for now, but it would cause more problems if you used size_t for the indices and lengths instead of int.

Answer 2

I find your code lacks clarity, at least to my eyes, largely due to issues with naming.

max() doesn't return a maximum value, it returns the index of the maximum. A more meaningful name would help readability.

swap() swaps two entries in an array using a fairly unexpressive approach - what was wrong with an intermediate int to swap the values with?

You work your way down the array, but use a loop based on incrementing.

I'll leave it to others to critique the actual sorting algorithm, though I wonder if there's anyway to provide an early exit once the array's actually sorted.

I don't have a C Compiler to hand, but here's a sketch of my revisions using Java, which in this case is probably close enough to illustrate.

package codeReview; import java.util.Arrays; public class MaxSort { private static int indexOfMaxElement(int arr1[], int limit) { int maxIndex = 0; for (int i = 0; i <= limit; i++) { maxIndex = (arr1[i] > arr1[maxIndex]) ? (i) : (maxIndex); } return maxIndex; } private static void swap(int arr[], int limit, int maxIndex) { if (arr[limit] != arr[maxIndex]) { int swap = arr[limit]; arr[limit] = arr[maxIndex]; arr[maxIndex] = swap; } } public static void main(String[] args) { int array[] = {1, 5, 7, 2, 8, 8, 9, 10, 32, 4, 4}; int len = array.length; for (int limit = len-1; limit > 0; limit--) { swap(array, limit, indexOfMaxElement(array, limit)); } System.out.println("Sorted Array:"); System.out.println(Arrays.toString(array)); } }