Distributed and Parallel Systems
Contribution: Week 6

Last week I was working in the Send File code, I changed the part of the clients and accept to many clients at the same time with threads and send the same file to several clients.

For this week I'm doing a quicksort in parallel.

Link to the wiki: (NULL)

Parallel Quicksort

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:
* Pick an element, called a pivot, from the list.
* Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
* Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

Like merge sort, quicksort can also be parallelized due to its divide-and-conquer nature. Individual in-place partition operations are difficult to parallelize, but once divided, different sections of the list can be sorted in parallel. The following is a straightforward approach: If we have P processors, we can divide a list of N elements into P sublists in O(n) average time, then sort each of these in average time.

One advantage of this simple parallel quicksort over other parallel sort algorithms is that no synchronization is required, but the disadvantage is that sorting is still O(n) and only a sublinear speedup of O(log n) is achieved. A new thread is started as soon as a sublist is available for it to work on and it does not communicate with other threads. When all threads complete, the sort is done.

This is the code. I will put this in the wiki.

#include <stdio.h>
#include <stdio.h>
#include <pthread.h>

int acomodar(int *v, int b, int t) {
  int i;
  int pivote, valor_pivote;
  int temp;

  pivote = b;
  valor_pivote = v[pivote];
  for (i=b+1; i<=t; i++){
    if (v[i] < valor_pivote){
      pivote++;
      temp = v[i];
      v[i] = v[pivote];
      v[pivote] = temp; 
    }
  }
  temp = v[b];
  v[b] = v[pivote];
  v[pivote] = temp;
  return pivote;
}

void *quick(int* v, int b, int t) {
  int pivote;
  int th;
  pthread_t thread1, thread2;
  if(b < t) {
    pivote = acomodar(v, b, t);
    th = pthread_create(&thread1, NULL, quick(v, b, pivote-1), NULL);
    th = pthread_create(&thread2, NULL, quick(v, pivote+1, t), NULL);
    pthread_exit(NULL);
  }
}

int main(int argc, char** args) {
  int arreglo[100];
  int i;
  for (i=0; i<100; i++) {
    arreglo[i] = rand()%10000;
  }

  quick(arreglo, 0, 99);
  for (i=0; i<100; i++) {
    printf("  %d", arreglo[i]);
  }
  printf("\n");
}

Comparison BubbleSort vs. QuickSort

I like this video because we can see how QuickSort is faster than the BubbleSort. Imagine quicksort in parallel, two robots helping to compare at the same time.