Сортировка двумерного массива по столбцу с использованием быстрого сортировки

Question

Я хочу сортировать двумерный массив по определенному столбцу, используя быструю сортировку. Я смог быстро выполнить сортировку для одномерного массива.

public class QuickSort1D { 

    public static void main(String[] args) { 
     int[] A = {9, 3, 10, 4, 1, 44, 12, 2, 90, 0}; 
     int l = 0; 
     int r = A.length-1; 
     QuickSort(A, l, r); 
     for (int i = 0; i < A.length; i++){ 
      System.out.print(A[i] + " "); 
     } 
    } 

    private static void QuickSort(int[] a, int l, int r) { 
     int i; 
     if (r > l){ 
      i = partition(a, l, r); 
      QuickSort(a, l, i-1); 
      QuickSort(a, i+1, r); 
     } 
    } 

    private static int partition(int[] a, int l, int r) { 
     int v = a[r]; 
     int i = l; 
     int j = r; 
     int temp; 
     while (i < j){ 
      while (a[i] < v){ 
       i = i + 1; 
      } 
      while ((i < j) && (a[j] >= v)){ 
       j = j - 1; 
      } 
      temp = a[i]; 
      if (i < j){ 
       a[i] = a[j]; 
       a[j] = temp; 
      }else{ 
       a[i] = a[r]; 
       a[r] = temp; 
      } 
     } 
     return i; 
    } 
} 

Для того, чтобы сделать это для двумерного массива, я должен будет включать в себя параметр для указанного столбца в методе QuickSort. Я не знаю, как исходить оттуда.

Например, массив изначально

{{4, 1, 3}, 
{6, 0, 2}, 
{5, 9, 8}} 

и массив отсортирован по колонке 2 должен быть

{{6, 0, 2}, 
{4, 1, 3}, 
{5, 9, 8}} 

Answer 1

Вы включаете параметр int column в ваш метод быстрой сортировки.

Затем вы просто заменяете каждый a[x] на a[x][column], тогда как метод подкачки (if else with temp) остается неизменным. Просто сделайте temp int[], а не int. И, конечно, тип a должен быть int[][] вместо int[].

Готово :)

Answer 2

Модифицированный код для сортировки 2D массива. Вы можете изменить значение columnToSort значение для изменения сортируемого столбца. Наслаждайтесь

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 

public class QuickSort1D { 
private static HashMap<Integer, List<Object>> array = new HashMap<Integer, List<Object>>(); 

public static void main(String[] args) { 
    int[][] A = { { 4, 1, 3 }, 
       { 6, 0, 2 }, 
       { 5, 9, 8 }, 
       { 5, 9, 8 }, 
       { 0, 1, 2 } }; 
    int l = 0; 
    int columnToSort = 0; 
    buildarray(A, columnToSort); 
    int r = array.keySet().size() - 1; 
    Integer[] sorted = QuickSort(array.keySet().toArray(new Integer[array.keySet().size()]), l, r); 
    for (int i = 0; i < sorted.length; i++) { 
     List<Object> k = array.get(sorted[i]); 
     for (Object object : k) { 
      int[] ar = (int[]) object; 
      for (int j : ar) { 
       System.out.print(j); 
      } 
      System.out.println(); 
     } 
     array.get(sorted[i]).remove(array.get(sorted[i]).size() - 1); 
    } 
} 

private static void buildarray(int[][] a, int columnToSort) { 
    for (int[] is : a) { 
     List<Object> ls = array.get(is[columnToSort]); 
     if (ls != null) { 
      ls.add(is); 
      continue; 
     } 
     ls = new ArrayList<Object>(); 
     ls.add(is); 
     array.put(is[columnToSort], ls); 
    } 

} 

private static Integer[] QuickSort(Integer[] a, int l, int r) { 
    int i; 
    if (r > l) { 
     i = partition(a, l, r); 
     QuickSort(a, l, i - 1); 
     QuickSort(a, i + 1, r); 
    } 
    return a; 
} 

private static int partition(Integer[] a, int l, int r) { 
    int v = a[r]; 
    int i = l; 
    int j = r; 
    int temp; 
    while (i < j) { 
     while (a[i] < v) { 
      i = i + 1; 
     } 
     while ((i < j) && (a[j] >= v)) { 
      j = j - 1; 
     } 
     temp = a[i]; 
     if (i < j) { 
      a[i] = a[j]; 
      a[j] = temp; 
     } else { 
      a[i] = a[r]; 
      a[r] = temp; 
     } 
    } 
    return i; 
} 
}