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));
  }
}