Japanese Verb Pairs

See Also

• Transitivity on Wikibooks.

Sorting Algorithms

Sorting is a common operation in many applications, and efficient algorithms to perform it have been developed.

Computer manufacturers of the 1960’s estimated that more than 25 percent of the running time of their computers was spent on sorting, when all their customers were taken into account. In fact, there were many installations in which the task of sorting was responsible for more than half of the computing time. From these statistics we may conclude that either

1. there are many important applications of sorting, or
2. many people sort when they shouldn’t, or
3. inefficient sorting algorithms have been in common use.

— Sorting and Searching, Knuth

Quicksort

• Worst-case performance: \(O(n^2)\)
• Average performance: \(O(n\log n)\)
• Best performance: \(O(n\log n)\)

Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved.

Implementation in C++

Implementation in Python

• C++
• Python

/* This function takes last element as pivot, places 
   the pivot element at its correct position in sorted 
    array, and places all smaller (smaller than pivot) 
   to left of pivot and all greater elements to right 
   of pivot */
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    // pivot 
    int i = (low - 1);  // Index of smaller element 
  
    for (int j = low; j <= high- 1; j++) 
    { 
        // If current element is smaller than or 
        // equal to pivot 
        if (arr[j] <= pivot) 
        { 
            i++;    // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
  
/* The main function that implements QuickSort 
 arr[] --> Array to be sorted, 
  low  --> Starting index, 
  high  --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        /* pi is partitioning index, arr[p] is now 
           at right place */
        int pi = partition(arr, low, high); 
  
        // Separately sort elements before 
        // partition and after partition 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 

# Python program for implementation of Quicksort Sort 
  
# This function takes last element as pivot, places 
# the pivot element at its correct position in sorted 
# array, and places all smaller (smaller than pivot) 
# to left of pivot and all greater elements to right 
# of pivot 
  
  
def partition(arr, low, high): 
    i = (low-1)         # index of smaller element 
    pivot = arr[high]     # pivot 
  
    for j in range(low, high): 
  
        # If current element is smaller than or 
        # equal to pivot 
        if arr[j] <= pivot: 
  
            # increment index of smaller element 
            i = i+1
            arr[i], arr[j] = arr[j], arr[i] 
  
    arr[i+1], arr[high] = arr[high], arr[i+1] 
    return (i+1) 
  
# The main function that implements QuickSort 
# arr[] --> Array to be sorted, 
# low  --> Starting index, 
# high  --> Ending index 
  
# Function to do Quick sort 
  
  
def quickSort(arr, low, high): 
    if len(arr) == 1: 
        return arr 
    if low < high: 
  
        # pi is partitioning index, arr[p] is now 
        # at right place 
        pi = partition(arr, low, high) 
  
        # Separately sort elements before 
        # partition and after partition 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 
  
  
# Driver code to test above 
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr, 0, n-1) 
print("Sorted array is:") 
for i in range(n): 
    print("%d" % arr[i]), 
  
# This code is contributed by Mohit Kumra
#This code in improved by https://github.com/anushkrishnav 

Mergesort

• Worst-case performance: \(O(n\log n)\)
• Average performance: \(O(n\log n)\)
• Best performance: \(O(n\log n)\)

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

Implementation in C++

Implementation in Python

• C++
• Python

void merge(int *,int, int , int );
void merge_sort(int *arr, int low, int high)
{
    int mid;
    if (low < high){
        //divide the array at mid and sort independently using merge sort
        mid=(low+high)/2;
        merge_sort(arr,low,mid);
        merge_sort(arr,mid+1,high);
        //merge or conquer sorted arrays
        merge(arr,low,high,mid);
    }
}
// Merge sort 
void merge(int *arr, int low, int high, int mid)
{
    int i, j, k, c[50];
    i = low;
    k = low;
    j = mid + 1;
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            c[k] = arr[i];
            k++;
            i++;
        }
        else  {
            c[k] = arr[j];
            k++;
            j++;
        }
    }
    while (i <= mid) {
        c[k] = arr[i];
        k++;
        i++;
    }
    while (j <= high) {
        c[k] = arr[j];
        k++;
        j++;
    }
    for (i = low; i < k; i++)  {
        arr[i] = c[i];
    }
}

# Python program for implementation of MergeSort
def mergeSort(arr):
    if len(arr) > 1:
 
         # Finding the mid of the array
        mid = len(arr)//2
 
        # Dividing the array elements
        L = arr[:mid]
 
        # into 2 halves
        R = arr[mid:]
 
        # Sorting the first half
        mergeSort(L)
 
        # Sorting the second half
        mergeSort(R)
 
        i = j = k = 0
 
        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
 
        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
 
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
 
# Code to print the list
 
 
def printList(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()

Euler Angles

Let \((\hat{\mathbf{x}},\hat{\mathbf{y}},\hat{\mathbf{z}})\) denote the spatial frame (does not rotate with the body) and \((\hat{\mathbf{x}}',\hat{\mathbf{y}}',\hat{\mathbf{z}}')\) denote the body frame.

The following two procedures of rotation are identical.

1. Rotate around \(\hat{\mathbf{z}}\) by \(\alpha\).
2. Rotate around \(\hat{\mathbf{y}}\) by \(\beta\).
3. Rotate around \(\hat{\mathbf{z}}\) by \(\gamma\).

vs.

1. Rotate around \(\hat{\mathbf{z}}\) by \(\gamma\).
2. Rotate around \(\hat{\mathbf{y}}'\) by \(\beta\).
3. Rotate around \(\hat{\mathbf{z}}''\) by \(\alpha\).

In particular, the point \((\theta,\varphi)\) on \(S^2\) may be obtained from both of the above procedures with \(\gamma = \varphi\) and \(\beta=\theta\).

This equivalence has applications in, for example, the Wigner \(D\) matrices.

Usage of Semicolons, Colons, and Dashes

This note is copied from Semicolons, colons, and dashes.

Semicolons

1. To help separate items in a list, when some of those items already contain commas.

I bought shiny, ripe apples; small, sweet, juicy grapes; and firm pears.

2. To join two sentences.

I went to the grocery store today. I bought a ton of fruit; apples, grapes, and pears were all on sale.

But NEVER DO THIS: I went to the grocery store today; I bought a ton of fruit; apples, grapes, and pears were all on sale.

Colons

1. To announce, introduce, or direct attention to a list, a noun or noun phrase, a quotation, or an example/explanation.

We covered many of the fundamentals in our writing class: grammar, punctuation, style, and voice.

2. To join sentences.

Life is like a puzzle: half the fun is in trying to work it out.

3. To express time, in titles, and as part of other writing conventions.

To Whom it May Concern: Please accept my application for the position advertised in the News and Observer.

NEVER DO THESE: Using a colon between a verb and its object or complement: The very best peaches are: those that are grown in the great state of Georgia.

Using a colon between a preposition and its object: My favorite cake is made of: carrots, flour, butter, eggs, and cream cheese icing.

Using a colon after "such as," "including," "especially," and similar phrases: There are many different types of paper, including: college ruled, wide ruled, and plain copy paper.

Dashes

1. To set off material for emphasis.

After eighty years of dreaming, the elderly man realized it was time to finally revisit the land of his youth—Ireland.

2. To indicate sentence introductions or conclusions.

To improve their health, Americans should critically examine the foods that they eat—fast food, fatty fried foods, junk food, and sugary snacks.

3. To mark "bonus phrases."

Even the simplest tasks—washing, dressing, and going to work—were nearly impossible after I broke my leg.

4. To break up dialogue.

Mimi began to explain herself, saying, “I was thinking—” “I don’t care what you were thinking,” Rodolpho interrupted.